Avec l'avènement des attaques par canaux auxiliaires, à la fin des années 90, les preuves de sécurité algébriques ne sont plus suffisantes pour garantir la sécurité de crypto-systèmes embarqués. L'une de ces attaques, la Differential Fault Analysis, propose d'exploiter les perturbations malicieuses de composants cryptographiques pour en extraire des données secrètes. L'objet de cette thèse est d'étendre le champ d'application de l'analyse de perturbations en proposant de nouvelles attaques basées sur des modèles de faute innovants mais réalistes. Alors qu'il est rapidement devenu nécessaire de protéger les clés privées contre les perturbations, de récents travaux ont démontré que la perturbation d'éléments publics pouvait aussi engendrer une fuite d'information critique. Dans ce cadre, nous nous intéresserons particulièrement aux implantations classiques de deux crypto-systèmes asymétriques des plus répandus : le RSA et le DSA. Nous étudierons leur comportement vis-à-vis de perturbations intervenant pendant leur exécution, ce qui n'avait jamais été fait auparavant. Dans un second temps, nous avons suivi l'émergence de nouveaux algorithmes de chiffrement à flot. La structure mathématique de ces nouveaux algorithmes étant désormais plus forte, nous avons voulu évaluer la robustesse de leur implantation face aux perturbations. A ce titre, nous nous sommes intéressés à deux des finalistes du projet eSTREAM : Grain-128 et Rabbit. Enfin, cette thèse soulignera la difficulté de protéger les implantations de crypto-systèmes contre les perturbations en prenant l'exemple du RSA-CRT.

Cette thèse se propose de remédier à l'absence de formalisme dédié aux preuves de sécurité concrète à travers 3 contributions. Nous présentons d'abord la logique CIL (Computational Indistinguishability Logic), qui permet de raisonner sur les systèmes cryptographiques. Elle contient un petit nombre de règles qui correspondent aux raisonnements souvent utilisés dans les preuves. Leur formalisation est basée sur des outils classiques comme les contextes ou les bisimulations. Deuxièmement, pour plus d'automatisation des preuves, nous avons conçu une logique de Hoare dédiée aux chiffrement asymétrique dans le modèle de l'oracle aléatoire. Elle est appliquée avec succès sur des exemples de schémas existants. Enfin, nous proposons un théorème générique de réduction pour la preuve d'indifférentiabilité d'un oracle aléatoire de fonctions de hachage cryptographiques. La preuve du théorème, formalisée en CIL, en démontre l'applicabilité. Les exemples de Keccak et Chop-Merkle-Damgard illustrent ce résultat.

L’externalisation des données dans le Cloud a engendré de nouvelles problématiques de sécurité. L’enjeu est de protéger les données des utilisateurs et leur vie privée. En ce sens, deux principes ont été suivis durant cette thèse : le premier est d’avoir une confiance limitée envers l’hébergeur de données (entre autres), le deuxième est d’établir une architecture basée sur un modulede confiance placé en rupture entre le poste client et le Cloud, d’où l’approche "Trust The Module,Not The Cloud" (TTM).Déléguer donc les opérations de sécurité à un module matériel dédié permet alors plusieurs bénéfices : d’abord s’affranchir d’un poste client davantage vulnérable face à des attaques internes ou externes ; ensuite limiter les composants logiciels au strict minimum afin d’avoir un meilleur contrôle du fonctionnement et enfin dédier les opérations cryptographiques à des co-processeurs spécialisés afin d’obtenir des performances élevées. Ainsi, les travaux menés durant cette présente thèse suivent trois axes. Dans un premieraxe nous avons étudié les défis d’un Cloud personnel destiné à protéger les données d’un particulier, et basé sur une carte nano-ordinateur du marché peu coûteuse. L’architecture que nous avons définie repose sur deux piliers : une gestion transparente du chiffrement grâce à l’usage d’un chiffrement par conteneur appelé Full Disk Encryption (FDE), initialement utilisédans un contexte de protection locale (chiffrement du disque d’un ordinateur ou d’un disque dur externe) ; et une gestion transparente de la distribution grâce à l’usage du protocole iSCSI qui permet de déporter le conteneur sur le Cloud. Nous avons montré que ces deux piliers permettent de construire un service sécurisé et fonctionnellement riche grâce à l’ajout progressif de modules"sur étagère" supplémentaires.Dans un deuxième axe, nous nous sommes intéressés au problème de performance lié à l’usage du FDE. Une étude approfondie du mode de chiffrement XTS-AES recommandé pour le FDE, du module noyau Linux dm-crypt et des co-processeurs cryptographiques (ne supportant pas tous le mode XTS-AES), nous ont conduit à proposer différentes optimisations dont l’approche extReq, qui étend les requêtes cryptographiques envoyées aux co-processeurs. Ces travaux nousont ainsi permis de doubler les débits de chiffrement et déchiffrement.Dans un troisième axe, afin de passer à l’échelle, nous avons utilisé un module de sécurité matériel (Hardware Secure Module ou HSM) certifié et plus puissant, dédié à la protection des données et à la gestion des clés. Tout en capitalisant sur l’architecture initiale, l’ajout du module HSM permet alors de fournir un service de protection adapté aux besoins d’une entreprise par exemple. / Data outsourcing to the Cloud has led to new security threats. The main concerns of this thesis are to protect the user data and privacy. In particular, it follows two principles : to decrease the necessary amount of trust towards the Cloud, and to design an architecture based on a trusted module between the Cloud and the clients. Both principles are derived from a new design approach : "Trust The Module, Not The Cloud ".Gathering all the cryptographic operations in a dedicated module allows several advantages : a liberation from internal and external attacks on client side ; the limitation of software to the essential needs offers a better control of the system ; using co-processors for cryptographic operations leads to higher performance.The thesis work is structured into three main sections. In the first section , we confront challenges of a personal Cloud, designed to protect the users’ data and based on a common and cheap single-board computer. The architecture relies on two main foundations : a transparent encryption scheme based on Full Disk Encryption (FDE), initially used for local encryption (e.g., hard disks), and a transparent distribution method that works through iSCSI network protocol in order to outsource containers in Cloud.In the second section we deal with the performance issue related to FDE. By analysing the XTS-AES mode of encryption, the Linux kernel module dm-crypt and the cryptographic co-processors, we introduce a new approach called extReq which extends the cryptographic requests sent to the co-processors. This optimisation has doubled the encryption and decryption throughput.In the final third section we establish a Cloud for enterprises based on a more powerful and certified Hardware Security Module (HSM) which is dedicated to data encryption and keys protection. Based on the TTM architecture, we added "on-the-shelf" features to provide a solution for enterprise.

Notre approche dans cette thèse était d'identifier où le chiffrement complètement homomorphe (FHE) pouvait être utilisé pour le domaine des sciences informatiques et de construire une plate-forme expérimentale qui nous permette de tester des algorithmes de traitement de l'information manipulant des données chiffrées. La première partie de cette thèse est consacrée à l'état de l'art. Nous présentons d'abord les systèmes de chiffrement homomorphes conçus avant 2008, puis nous présentons ceux adressant la problématique du chiffrement complètement homomorphe. Nous décrivons plusieurs méthodes de chiffrement d'intérêt pour cette thèse et discutons de leurs implémentations FHE. Enfin, nous présentons des circuits de Yao car ils peuvent résoudre des problèmes similaires que le FHE et nous parlons brièvement du chiffrement fonctionnel (FE). La deuxième partie de cette thèse présente nos contributions. Nous commençons par expliquer comment le FHE peut être utile dans divers scénarios et décrivons plusieurs cas d'utilisation pratique identifiés au cours de la thèse. Ensuite, nous décrivons notre approche pour effectuer des calculs sur des données chiffrées à l'aide du FHE et expliquons comment nous avons pu développer une plate-forme pour l'exécution dans le domaine chiffré d'une large gamme d'algorithmes en s'appuyant seulement sur l'addition et la multiplication homomorphes. Nous détaillons ensuite notre solution pour effectuer des requêtes privées sur une base de données chiffrées en utilisant le chiffrement homomorphe. Dans un dernier chapitre, nous présentons nos résultats expérimentaux. / Our approach in this thesis was to identify where FHE could be used in computer science and to build an experimental platform that allow us to test real-life algorithm running on homomorphically-encrypted data. The first part of this thesis is dedicated to the state of the art. We first present homomorphic encryption schemes designed before 2008 and then move to the Fully Homomorphic Encryption period. We describe several schemes of interest for this thesis and discuss FHE implementations. Finally, we present Yao’s garbled circuits as they can solve similar problems as FHE and briefly talk about Functional Encryption (FE). The second part of this thesis is for our contributions to the subject. We begin by explaining how FHE can be useful in various scenarios and try to provide practical use cases that we identified during the thesis. Then, we describe our approach to perform computations on encrypted data using FHE and explain how we were able to build on just the homomorphic addition and multiplication a platform for the execution in the encrypted domain of a wide range of algorithms. We then detail our solution for performing private queries on an encrypted database using homomorphic encryption. In a final chapter, we present our experimental results.

Cette thèse se propose de remédier à l'absence de formalisme dédié aux preuves de sécurité concrète à travers 3 contributions. Nous présentons d'abord la logique CIL (Computational Indistinguishability Logic), qui permet de raisonner sur les systèmes cryptographiques. Elle contient un petit nombre de règles qui correspondent aux raisonnements souvent utilisés dans les preuves. Leur formalisation est basée sur des outils classiques comme les contextes ou les bisimulations. Deuxièmement, pour plus d'automatisation des preuves, nous avons conçu une logique de Hoare dédiée aux chiffrement asymétrique dans le modèle de l'oracle aléatoire. Elle est appliquée avec succès sur des exemples de schémas existants. Enfin, nous proposons un théorème générique de réduction pour la preuve d'indifférentiabilité d'un oracle aléatoire de fonctions de hachage cryptographiques. La preuve du théorème, formalisée en CIL, en démontre l'applicabilité. Les exemples de Keccak et Chop-Merkle-Damgard illustrent ce résultat. / In this thesis, we address the lack of formalisms to carry out concrete security proofs. Our contributions are threefold. First, we present a logic, named Computational Indistinguishability Logic (CIL), for reasoning about cryptographic systems. It consists in a small set of rules capturing reasoning principles common to many proofs. Their formalization relies on classic tools such as bisimulation relations and contexts. Second, and in order to increase proof automation, it presents a Hoare logic dedicated to asymmetric encryption schemes in the Random Oracle Model that yields an automated and sound verification method. It has been successfully applied to existing encryption schemes. Third, it presents a general reduction theorem for proving indifferentiability of iterative hash constructions from a random oracle. The theorem is proven in CIL demonstrating the usefulness of the logic and has been applied to constructions such as the SHA-3 candidate Keccak and the Chop-MD construction.

Le retrait d’information privé que nous nommons PIR, désigne un groupe de protocoles qui s’inscrit dans un ensemble plus vaste des technologies d’amélioration de la vie privée. Sa fonctionnalité principale est de dissimuler l’index d’un élément d’une liste accédée par un client au regard de son hôte. Sans négliger l’appart de leurs auteurs à la communauté scientifique, l’utilisabilité de ce groupe de protocoles semble limitée, car pour un client, télécharger l’intégralité de la liste est plus efficient. À ce jour, les PIR, se fondent sur des serveurs répliqués mutuellement méfiants, des périphériques de confiance ou bien des systèmes cryptographiques. Nous considérerons ici les retraits d’informations privés computationnels et plus particulièrement ceux reposant sur les réseaux euclidiens qui n’offrent des propriétés particulières, comme l’homomorphisme. Afin d’en démontrer l’utilisabilité, nous proposons un retrait d’information privé reposant sur un système cryptographique homomorphe performant et aisé d’utilisation / Private information retrieval, named PIR, is a set of protocols that is a part of privacy enhancement technologies.Its major feature is to hide the index of a record that a user retrieved from the host.Without neglecting the scientific contributions of its authors, the usability of this protocol seems hard since that, for a user, it seems more and more efficient to receive all the records.Thus far, PIR can be achieved using mutually distrustful databases replicated databases, trusted hardware, or cryptographic systems.We focus on computational private information retrieval, and specifically on thus based on cryptographic systems.This decision is contingent to the spread of cryptographic systems based on lattices who provide specific properties.To demonstrate it usability, we offer an efficient and easy-to-use private Information retrieval based on homomorphic encryption.

Avec la possibilité de l’existence d’un ordinateur quantique, les primitives cryptographiques basées sur la théorie des nombres risquent de devenir caduques. Il devient donc important de concevoir des schémas résistants à ce nouveau type de menaces. Les réseaux euclidiens et les codes correcteurs d’erreurs sont deux outils mathématiques permettant de construire des problèmes d’algèbre linéaire, pour lesquels il n’existe aujourd’hui pas d’algorithme quantique permettant d’accélérer significativement leur résolution. Dans cette thèse, nous proposons quatre primitives cryptographiques de ce type : deux schémas de signatures (dont une signature traçable) basés sur les réseaux, un protocole de délégation de signature utilisant du chiffrement complètement homomorphe, et une nouvelle approche permettant de construire des cryptosystèmes très efficaces en pratique basés sur les codes. Ces contributions sont accompagnées de paramètres concrets permettant de jauger les coûts calculatoires des primitives cryptographique dans un monde post-quantique. / In the likely event where a quantum computer sees the light, number theoretic based cryptographic primitives being actually in use might become deciduous. This results in an important need to design schemes that could face off this new threat. Lattices and Error Correcting Codes are mathematical tools allowing to build algebraic problems, for which – up to-date – no quantum algorithm significantly speeding up their resolution is known. In this thesis, we propose four such kind cryptographic primitives: two signatures schemes (among those a traceable one) based on lattices, a signature delegation protocol using fully homomorphic encryption, and a new framework for building very efficient and practical code-based cryptosystems. These contributions are fed with concrete parameters allowing to gauge the concrete costs of security in a post-quantum world.

Les fonctions non clonables physiquement, appelées PUF (Physically Unclonable Functions), représentent une technologie innovante qui permet de résoudre certains problèmes de sécurité et d’identification. Comme pour les empreintes humaines, les PUF permettent de différencier des circuits électroniques car chaque exemplaire produit une signature unique. Ces fonctions peuvent être utilisées pour des applications telles que l’authentification et la génération de clés cryptographiques. La propriété principale que l’on cherche à obtenir avec les PUF est la génération d’une réponse unique qui varie de façon aléatoire d’un circuit à un autre, sans la possibilité de la prédire. Une autre propriété de ces PUF est de toujours reproduire, quel que soit la variation de l’environnement de test, la même réponse à un même défi d’entrée. En plus, une fonction PUF doit être sécurisée contre les attaques qui permettraient de révéler sa réponse. Dans cette thèse, nous nous intéressons aux PUF en silicium profitant des variations inhérentes aux technologies de fabrication des circuits intégrés CMOS. Nous présentons les principales architectures de PUF, leurs propriétés, et les techniques mises en œuvre pour les utiliser dans des applications de sécurité. Nous présentons d’abord deux nouvelles structures de PUF. La première structure appelée “Loop PUF” est basée sur des chaînes d’éléments à retard contrôlés. Elle consiste à comparer les délais de chaînes à retard identiques qui sont mises en série. Les points forts de cette structure sont la facilité de sa mise en œuvre sur les deux plates-formes ASIC et FPGA, la grande flexibilité pour l’authentification des circuits intégrés ainsi que la génération de clés de chiffrement. La deuxième structure proposée “TERO PUF” est basée sur le principe de cellules temporairement oscillantes. Elle exploite la métastabilité oscillatoire d’éléments couplés en croix, et peut aussi être utilisée pour un générateur vrai d’aléas (TRNG). Plus précisément, la réponse du PUF profite de la métastabilité oscillatoire introduite par une bascule SR lorsque les deux entrées S et R sont connectées au même signal d’entrée. Les résultats expérimentaux montrent le niveau de performances élevé des deux structures de PUF proposées. Ensuite, afin de comparer équitablement la qualité des différentes PUF à retard, nous proposons une méthode de caractérisation spécifique. Elle est basée sur des mesures statistiques des éléments à retard. Le principal avantage de cette méthode vient de sa capacité à permettre au concepteur d’être sûr que la fonction PUF aura les performances attendues avant sa mise en œuvre et sa fabrication. Enfin, en se basant sur les propriétés de non clonabilité et de l’imprévisibilité des PUF, nous présentons de nouvelles techniques d’authentification et de génération de clés de chiffrement en utilisant la “loop PUF” proposée. Les résultats théoriques et expérimentaux montrent l’efficacité des techniques introduites en termes de complexité et de fiabilité / Physically Unclonable Functions, or PUFs, are innovative technologies devoted to solve some security and identification issues. Similarly to a human fingerprint, PUFs allows to identify uniquely electronic devices as they produce an instance-specific signature. Applications as authentication or key generation can take advantage of this embedded function. The main property that we try to obtain from a PUF is the generation of a unique response that varies randomly from one physical device to another without allowing its prediction. Another important property of these PUF is to always reproduce the same response for the same input challenge even in a changing environment. Moreover, the PUF system should be secure against attacks that could reveal its response. In this thesis, we are interested in silicon PUF which take advantage of inherent process variations during the manufacturing of CMOS integrated circuits. We present several PUF constructions, discuss their properties and the implementation techniques to use them in security applications. We first present two novel PUF structures. The first one, called “Loop PUF” is a delay based PUF which relies on the comparison of delay measurements of identical serial delay chains. The major contribution brought by the use of this structure is its implementation simplicity on both ASIC and FPGA platforms, and its flexibility as it can be used for reliable authentication or key generation. The second proposed structure is a ring-oscillator based PUF cells “TERO PUF”. It exploits the oscillatory metastability of cross-coupled elements, and can also be used as True Random Number Generator (TRNG). More precisely, the PUF response takes advantage from the introduced oscillatory metastability of an SR flip-flop when the S and R inputs are connected to the same input signal. Experimental results show the high performance of these two proposed PUF structures. Second, in order to fairly compare the quality of different delay based PUFs, we propose a specific characterization method. It is based on statistical measurements on basic delay elements. The main benefit of this method is that it allows the designer to be sure that the PUF will meet the expected performances before its implementation and fabrication. Finally, Based on the unclonability and unpredictability properties of the PUFs, we present new techniques to perform “loop PUF” authentication and cryptographic key generation. Theoretical and experimental results show the efficiency of the introduced techniques in terms of complexity and reliability

Dans cette thèse, on s'intéresse à des schémas de chiffrement par blocs, c'est-à-dire que le chiffrement (et le déchiffrement) envoie un bloc de n bits sur un bloc de n bits. Il y a essentiellement deux grandes structures utilisées pour un schéma de chiffrement par blocs : la structure de Feistel (utilisée pour le DES) et la structure SPN (utilisée pour l'AES). L'étude de la sécurité de ces différents structures et schémas a permis de nombreuses avancées autant pratiques que théoriques. Nous présentons dans cette thèse des preuves de sécurité pour le schéma d'Even-Mansour itéré, le schéma paramétrable CLRW et le schéma de Feistel à clés alternées. Ces preuves utilisent une technique probabiliste, appelée coupling, introduite en cryptographie en 2002 par Mironov. Nous présentons cette technique dans le cadre des probabilités, puis la façon d'utiliser le coupling pour prouver la sécurité des schémas cités précédemment. Nous présentons également une étude de la sécurité du schéma d'Even-Mansour à deux tours pour certaines minimisations (même clés de tours ou même permutations internes par exemple) et, pour conclure, une comparaison des différentes techniques d'indistinguabilité / In this thesis, we study blockciphers, meaning that the encryption (and decryption) sends a block of n bits on a block of n bits. There is essentially two main structures used for a blockcipher: the Feistel structure (used for DES) and the SPN structure (used for AES). The study of the security of these structures and schemes has led to many practical and theoretical advances. We present in this thesis proofs of security for the iterated Even-Mansour scheme, the tweakable blockcipher CLRW and the key-alternating Feistel cipher. These proofs use a probabilistic technique, called coupling, introduced in cryptography in 2002 by Mironov. We present this technique in the context of probabilities, then we present how to use the coupling to prove the security for the schemes mentioned above. We also present an analysis of the security of the Even-Mansour cipher with two rounds and some properties (same round keys or same internal permutations for example) and, finally, we compare the different techniques to prove indistinguishability

La transmission de données multimédia sur les réseaux sécurisés a une croissance exponentielle grâce aux progrès scientifique dans les technologies de l'information et de la communication. La sécurité des données dans certaines applications comme le stockage sécurisé, l'authentification, la protection des droits d'auteurs, la communication militaire ou la visioconférence confidentielles, nécessitent de nouvelles stratégies en matière de transmission sécurisée. Deux techniques sont couramment utilisées pour la transmission sécurisée de données visuelles, à savoir : la cryptographie et la stéganographie. La cryptographie sécurise les données en utilisant des clés secrètes afin de rendre les données illisibles, la stéganographie, elle, vise à insérer des données cruciales dans des signaux porteurs anodins.De plus, pour la confiance mutuelle et les systèmes distribués, le partage sécurisé de ressources est souvent une garantie suffisante pour les applications de communication. L'objectif principal de cette thèse est de réaliser une protection des données visuelles, en particulier les images numériques, par le biais des techniques modernes de cryptographie. Dans ce contexte, deux objectifs de recherche ont été développés durant ces travaux de thèse.La première partie de notre travail se concentre sur la sécurité des images numériques dans un environnement partagé. Ensuite, la deuxième partie porte sur l'intégrité des données visuelles pendant une transmission sécurisée.Nous avons proposé un nouveau schéma de partage des images qui exploite les propriétés d'addition et de multiplication homomorphique de deux crypto systèmes à clé publique largement utilisés : les algorithmes RSA et Paillier. Dans les schémas traditionnels de partage sécurisé, le ``dealer'' partitionne le secret en parties et le distribue à chacun des autres acteurs. Ainsi, aucun des acteurs impliqués ne participe à la création du partage sécurisé, mais il est toujours possible que le ``dealer'' transmette des données malveillantes. Au contraire, l'approche proposée utilise le système de partage de secret d'une manière qui limite l'influence du ‘‘dealer'' sur le protocole en permettant à chaque acteur de participer.La deuxième partie de ces travaux de thèse met l'accent sur l'intégrité des données visuelles lors de la transmission. L'intégrité des données signifie que les données gardent leurs structures complètes au cours d'une opération numérique comme le stockage, le transfert ou la récupération. Le changement d'un seul bit de données cryptées peut avoir un impact catastrophique sur les données décryptées. Nous abordons le problème de correction d'erreurs dans les images cryptées en utilisant le chiffrement à clé symétrique AES (Advanced Encryptions Standard) suivant différents modes. Trois mesures sont proposées afin d'exploiter les statistiques locales des données visuelles et l'algorithme de chiffrement, dans l'objectif de corriger les erreurs efficacement. / Due to the advancements in the information and communication technologies, the transmission of multimedia data over secure or insecure communication channels has increased exponentially. The security of data in applications like safe storage, authentications, copyright protection,remote military image communication or confidential video-conferencing require new strategies for secure transmission. Two techniques are commonly used for the secure transmission of visual data, i.e. cryptography and steganography. Cryptography achieves security by using secret keysto make the data illegible while steganography aims to hide the data in some innocent carrier signal. For shared trust and distributed environment, secret sharing schemes provide sufficient security in various communication applications. The principal objective of this thesis is to achieveprotection of visual data especially images through modern cryptographic techniques. In this context, the focus of the work in perspective, is twofolded. The first part of our work focuses on the security of image data in shared environment while the second part focuses on the integrity ofimage data in the encrypted domain during transmission.We proposed a new sharing scheme for images which exploits the additive and multiplicative homomorphic properties of two well known public key cryptosystems, namely, the RSA and the Paillier. In traditional secret sharing schemes, the dealer partitions the secret into shares and distributethe shares to each of the player. Thus, none of the involved players participate in the creation of the shared secret and there is always a possibilitythat the dealer can cheat some player. On the contrary, the proposed approach employs the secret sharing scheme in a way that limits the influence of the dealer over the protocol by allowing each player to participate. The second part of our thesis emphasizes on the integrity of visual data during transmission. Data integrity means that the data have its complete structure during any operation like storage, transfer or retrieval. A single bit change in encrypted data can have catastrophic impact over the decrypted data. We address the problem of error correction in images encrypted using symmetric key cryptosystem of the Advanced Encryption Standard (AES) algorithm. Three methods are proposed to exploit the local statistics of the visual data and the encryption algorithm to successfully correct the errors.