L'objectif de ce travail est de fournir des modèles et outils pour simplifier la construction des systèmes distribués à base de composants sécurisés, ainsi que la gestion des propriétés de sécurité, en utilisant des outils de haut niveau d'abstraction pour la configuration et la reconfiguration dynamique. En plus des propriétés d'accessibilité et de communications sécurisées classiques, nous focalisons notre travail sur une propriété des systèmes répartis plus générale : la non-interférence. Cette propriété atteste qu'il ne doit pas y avoir de flux d'information entre des parties publiques et privées du système. Ce qui implique le suivi de l'acheminement de l'information entre les différentes composantes du système distribué. Notre objectif principal est donc de proposer un modèle, accompagné d'un ensemble d'outils, garantissant la propriété de la non-interférence à la construction du système, et ce à une plus grosse granularité : celle des composants. Ces outils permettent de (1) configurer les paramètres de sécurité des composants et des liaisons entre eux, (2) vérifier la propriété de non-interférence dans le code d'un composant et entre les différents composants du système et (3) générer automatiquement le code nécessaire pour appliquer ces propriétés de sécurité. D'autre part, nous proposons une architecture permettant de vérifier dynamiquement la propriété de non-interférence dans un système réparti. / The goal of this thesis is to provide models and tools to simplify secured component-based distributed systems' construction and the management of their security properties, by using high-level tools for dynamic configuration and reconfiguration. In addition to the classic properties of accessibility and secured communications, we focus on a more general security property of distributed systems : the non-interference. This property says that there mustn't be information flow between secret and public parts of the system ; which requires information flow control across the system. Our main objective is to propose a model and set of tools guarantying the non-interference property at compiletime, and at a bigger granularity : the components. These tools are (1) tools for configuring security parameters of components and binding between components, (2) a compiler checking the non-interference property, and (3) tools for automatic generation of code assuring these security properties. On the other hand, we present an architecture enabling a dynamic verification of the non-interference property in a distributed system.

Cette thèse porte sur les attaques par observations. Ces attaques étudient les variations d'émanation d'un composant pour retrouver une clé secrète. Ces émanations peuvent être multiples, par exemple, la consommation de courant électrique, le rayonnement électromagnétique, etc. Généralement, ces attaques font appel à des méthodes statistiques pour examiner la relation entre les émanations du composant et des modèles de consommation imaginés par l'attaquant. Trois axes sont développés dans cette thèse. Dans un premier temps, nous avons implémenté différentes attaques par observations sur des cartes graphiques en utilisant l'API OpenCL. Ces implémentations sont plus performantes que les implémentations classiques, ce qui permet à un attaquant de pouvoir traiter plus de données. Dans un second temps, nous avons proposé l'utilisation du MIC dans le cadre des attaques par observations. L'avantage du MIC, par rapport à l'information mutuelle, est sa facilité de calcul, ne dépendant pas de choix de noyau ou de taille de fenêtre. Son utilisation dans une attaque par observations est donc aisée, même si, la complexité des calculs à effectuer est souvent très importante. Enfin, nous avons introduit une nouvelle attaque, basée sur la distribution jointe de l'entrée et de la sortie de fonction cryptographique. Si cette distribution varie en fonction de la valeur de la clé impliquée par la fonction, on est capable de retrouver la clé secrète utilisée par le composant. Cette nouvelle attaque a la particularité de ne nécessiter ni la connaissance du texte clair, ni la connaissance du texte chiffré, ce qui lui permet d'être efficace même en présence de certaines contre-mesures. / The main subject of this manuscript is the Side Channel Attacks. These attacks investigate the variation of device emanations to retrieve a secret key. These emanations can be the power consumption, the electromagnetic radiation, etc. Most of the time, those attacks use statistical methods to examine the relationship between the emanations and some leakage models supposed by the attacker. Three main axis are developed here. First, we have implemented many side channel attacks on GPGPU using the API OpenCL. These implementations are more effective than the classical ones, so an attacker can exploit more data. Then, in order to provide a new side channel attack, we have suggested the use of a new dependency measurement proposed by Reshef et al., the MIC. The MIC is more advantageous than the mutual information, because its computation does not depend of a kernel choice nor a windows size. So, its use in side channel analysis is simple, even if the time complexity is large. Finally, we have introduced a new attack based on the join distribution of the input and the output of a cryptographic sub-function. If the distribution depends on the key used in the function, we can retrieve the secret key. This attack can be efficient even in presence of some countermeasures because it does not required the knowledge of both plain text or cipher text.

Je souhaite réaliser un modèle théorique optimal pour les protocoles de partage de secret quantique basé sur l'utilisation des états graphes. Le paramètre représentatif d'un partage de secret à seuil est, entre autres la taille du plus grand ensemble de joueurs qui ne peut pas accéder au secret. Je souhaite donc trouver un famille de protocoles pour laquelle ce paramètre est le plus petit possible. J'étudie également les liens entre les protocoles de partage de secret quantique et des familles de courbes en géométrie algébrique. / I want to realize an optimal theoretical model for quantum secret sharing protocols based on graph states. The main parameter of a threshold quantum secret sharing scheme is the size of the largest set of players that can not access the secret. Thus, my goal is to find a collection of protocols for which the value of this parameter is the smallest possible. I also study the links between quantum secret sharing protocols and families of curves in algebraic geometry.

Les échanges des informations confidentielles ou critiques dans un environnement public, et donc potentiellement hostile, nécessitent l'emploi de techniques cryptographiques (protocoles et primitives). Malheureusement, l'expérience montre qu'une mauvaise conception, ou une expression peu claire des propriétés et hypothèses de sécurité attendues conduisent à des attaques, et qu'il faut parfois des années avant que celles-ci soient découvertes et corrigées. D'où l'adoption croissante de la sécurité prouvable, où on donne une définition rigoureuse des objectifs de sécurité et des démonstrations mathématiques que ceux-ci sont remplis. Par ailleurs, la complexité et la diversité des systèmes cryptographiques croît également. Il est donc largement admis qu'il n'est plus viable d'écrire ou vérifier manuellement des démonstrations cryptographiques (Bellare& Rogaway 2004, Shoup 2004, Halevi 2005) et qu'il faut développer des méthodes de vérification des systèmes cryptographiques assistées par ordinateur. L'objectif de cette thèse est d'effectuer des progrès significatifs dans cette direction. Plus précisement on s'interesse à la preuve formelle de protocoles cryptographiques. Vérifier des protocoles cryptographiques requiert le développement d'un cadre théorique qui doit permettre: - une modélisation précise des protocoles cryptographiques et des propriétés de sécurité qu'on veut prouver dans le modèle calculatoire. - mise en place de stratégies d'automatisation de preuves. - prise en compte des modèles plus réalistes pour l'adversaire (canaux cachés, ressources de calcul). A la fin de la thèse on a obtenu un cadre formel et un ensemble de méthodes logicielles capable d'aider à la vérification des protocoles cryptographiques. / Critical and private information are exchanged on public environment. To protect it from dishonest users, we use cryptographic tools. Unfortunately, bad conception, poorly written security properties and required security hypothesis lead to attacks, and it may take years before one discover the attack and fix the security schemes involved. In this context, provable security provides formal definitions for security objectives and implied mathematical proofs that these objectives are fullfilled. On another hand, complexity and variety of cryptographic systems are increasing, and proofs by hand are too complicated to write and to verify (Bellare& Rogaway 2004, Shoup 2004, Halevi 2005). Thus, we need computer-assisted verification methods for cryptographic systems. The aim of this thesis is to progress in this direction. More precisely we want significant progress over formal proofs on cryptographic protocols. To verify cryptographic protocols we need to develop a theoritical framework providing: - a precise modelisation for cryptographic protocols and security properties we want to prove in the computationnal model, - designing tactics to automate proofs, - taking into account realistic models for adversary (side-channels...). By the end of the thesis we have enhanced a theoretical framework and computing tools helping verifying cryptographic protocols.

Dans cette thèse,nous étudions comment exploiter des contraintes spatio-temporelles,notamment le principe d'impossibilité de transmission supraluminique,dans le but de créer des primitives cryptographiques sûres,par exemple la vérification de position ou la "mise en gage de bit''(bit commitment). D'après le principe d'impossibilité de transmission supraluminique,aucun vecteur physique d'information ne peut voyager plus vite que la vitesse de la lumière. Ce principe entraîne une contrainte sur le temps de communication entre deux points éloignés. Ce délai dans le transfert d'information peut être utilisé comme une contrainte temporelle interdisant la communication. En cryptographie multi-agents,il est connu que l'hypothèse de non-communication entre les agents permet de réaliser de manière sécurisée de nombreuses primitives comme la "mise en gage de bit'' et l'un des buts de cette thèse est de comprendre à quel point les contraintes spatio-temporelles peuvent être exploitèes pour simuler des scénarios de non-communication. Dans la première partie de cette thèse nous étudions comment utiliser une contrainte de non-communication pour essayer de vérifier la position d'une personne.Dans la dernière partie,nous nous penchons sur deux exemples de protocoles de ``mise en gage de bit'' relativistes afin d'en étudier la sécurité contre des adversaires classiques. Pour conclure cette thèse,nous mentionnons quelques problèmes ouverts intéréssants. Ces problèmes ouverts peuvent être très utiles pour comprendre le rôle de contraintes spatio-temporelles,par exemple de l'impossibilité de transmission supraluminique,dans la conception de primitives cryptographiques parfaitement sûres. / In this thesis we have studied how to exploit relativistic constraints such as the non-superluminal signalling principle to design secure cryptographic primitives like position-verification and bit commitment. According to non-superluminal signalling principle, no physical carrier of information can travel faster than the speed of light. This put a constraint on the communication time between two distant stations. One can consider this delay in information transfer as a temporal non-communication constraint. Cryptographic primitives like bit-commitment, oblivious transfer can be implemented with perfect secrecy under such non-communication assumption between the agents. The first part of this thesis has studied how non-signalling constraints can be used for secure position verification. Here, we have discussed about a strategy which can attack any position verification scheme. In the next part of this thesis we have discussed about the nonlocal games, relevant for studying relativistic bit commitment protocols. We have established an upper bound on the classical value of such family of games. The last part of this thesis discusses about two relativistic bit commitment protocols and their security against classical adversaries. We conclude this thesis by giving a brief summary of the content of each chapter and mentioning interesting open problems. These open problems can be very useful for better understanding of the role of spacetime constraints such as non-superluminal signalling in designing perfectly secure cryptographic primitives.

Les systèmes cryptographiques à base de courbes elliptiques sont aujourd'hui de plus en plus employés dans les protocoles utilisant la cryptographie à clef publique. Ceci est particulièrement vrai dans le monde de l'embarqué qui est soumis à de fortes contraintes de coût, de ressources et d'efficacité, car la cryptographie à base de courbes elliptiques permet de réduire significativement la taille des clefs utilisées par rapport aux systèmes cryptographiques précédemment employés tels que RSA (Rivest-Shamir-Adleman). Les travaux qui suivent décrivent dans un premier temps l'implantation efficace et sécurisée de la cryptographie à base de courbes elliptiques sur des composants embarqués, en particulier des cartes à puce. La sécurisation de ces implantations nécessite de prendre en compte les attaques physiques dont un composant embarqué peut être la cible. Ces attaques incluent notamment les analyses par canaux auxiliaires qui consistent à observer le comportement d'un composant pendant qu'il manipule une valeur secrète pour en déduire de l'information sur celle-ci, et les analyses par faute dans lesquelles un attaquant peut perturber un composant dans le même but.Dans la seconde partie de ce mémoire de thèse, nous étudions ces attaques et leurs implications concernant l'implantation des systèmes cryptographiques à clef publique les plus répandus. De nouvelles méthodes d'analyse et de nouvelles contre-mesures sont en particulier proposées. Une étude spécifique de certaines attaques appliquées à l'algorithme de chiffrement par bloc AES est également présentée. / Elliptic curve based cryptosystems are nowadays increasingly used in protocols involving public-key cryptography. This is particularly true in the context of embedded devices which is subject to strong cost, resources, and efficiency constraints, since elliptic curve cryptography requires significantly smaller key sizes compared to other commonly used cryptosystems such as RSA.The following study focuses in a first time on secure and efficient implementation of elliptic curve cryptography in embedded devices, especially smart cards. Designing secure implementations requires to take into account physical attacks which can target embedded devices. These attacks include in particular side-channel analysis which may infer information on a secret key manipulated by a component by monitoring how it interacts with its environment, and fault analysis in which an adversary can disturb the normal functioning of a device in the same goal.In the second part of this thesis, we study these attacks and their impact on the implementation of the most used public-key cryptosystems. In particular, we propose new analysis techniques and new countermeasures for these cryptosystems, together with specific attacks on the AES block cipher.

La cryptographie basée sur les réseaux a connu depuis quelques années un très fort développement notamment du fait qu’il existe des systèmes cryptographiques basés sur les réseaux avec des propriétés de sécurité plus fortes que dans les cas plus classiques de théorie des nombres. Les problèmes difficiles des réseaux, par exemple le problème de trouver des vecteurs courts non nuls, semblent résister aux attaques utilisant des ordinateurs quantiques et les meilleurs algorithmes qui existent pour les résoudre sont exponentiels en fonction du temps. L’objet de cette thèse est la construction de primitives cryptographiques à clé publique pour l’ano- nymat dont la sécurité repose sur des problèmes difficiles des réseaux.Nous nous intéressons aux schémas de signature de cercle. Tout d’abord, nous proposons une nouvelle définition d’anonymat et nous exposons un nouveau schéma de signature de cercle. Ensuite, nous donnons une étude de sécurité rigoureuse suivant deux définitions de résistance la contrefaçon. La première est la résistance à la contrefaçon contre les attaques à sous-cercles choisis et la deuxième est la résistance à la contrefaçon contre les attaques de corruption interne.Nous présentons ensuite un nouveau schéma d’identification de cercle et nous développons une analyse complète de sa sécurité. Enfin, nous montrons que les techniques utilisées pour construire le schéma précédent peuvent être utilisées pour construire un schéma d’identification de cercle à seuil. / Lattice-based cryptography has known during the last decade rapid develop- ments thanks to stronger security properties. In fact, there exist lattice-based cryp- tographic systems whose security is stronger than those based on the conventional number theory approach. The hard problems of lattices, for example the problem of finding short non-zero vectors, seems to resist quantum computers attacks. Mo- reover, the best existing algorithms solving them are exponential in time. The pur- pose of this thesis is the construction of public key cryptographic primitives for anonymity, whose security is based on the latter.In particular, we are interested in ring signature schemes. First, we propose a new formal definition of anonymity and we present a new ring signature scheme. Second, we give a rigorous study of security, following two definitions of unfor- geability. The first of which is unforgeability against chosen-subring attacks and the other one is unforgeability with respect to insider corruption.Afterwards, we present a new ring identification scheme and we develop a full analysis of its security. Finally, we show that the techniques used to build this scheme, can be used to construct a threshold ring identification scheme.

Les techniques de chiffrement les plus utilisées en cryptographie, basées sur des problèmes de théorie des nombres, présentent malgré leur efficacité des défauts notamment une vulnérabilité aux attaques menées à l'aide d'ordinateur quantiques. Il est donc pertinent d'étudier d'autres familles de cryptosystèmes. Nous nous intéressons ici aux cryptosystèmes basés sur les codes correcteurs, introduits par McEliece en 1978 qui, étant basés sur des problèmes difficiles de théorie des codes, ne présentent pas cette vulnérabilité. Ces cryptosystèmes présentent des inconvénients, qui font qu'ils sont peu utilisés en pratique. Selon le code choisi, ils peuvent être vulnérables aux attaques structurelles, mais surtout ils nécessitent des clés de taille très importante.Récemment une nouvelle famille de codes appelés codes MDPC a été introduite ainsi qu'un cryptosystème basé sur cette famille de codes. Les codes MDPC semblent être distinguables seulement en trouvant des mots de poids faibles dans leur dual, les affranchissant ainsi d'une éventuelle vulnérabilité aux attaques structurelles. De plus, en utilisant une des matrices quasi-cycliques, ils obtiennent des clés de taille très compacte.Nous avons pour notre part, travaillé dans le contexte de la métrique rang, une nouvelle métrique introduite en 1985 par Gabidulin qui semble bien adaptée à une utilisation en cryptographie :• Nous avons commencé par travailler autour de la notion de polynôme de Ore et le cas particulier important des q-polynômes. Ces derniers sont des combinaisons linéaires des itérés de l'automorphisme de Frobenius sur un corps fini.Ces polynômes constituent un objet d'étude important en métrique rang, de par leur utilisation dans les premiers cryptosystèmes dans cette métrique. Nous présentons sous une nouvelle forme des résultats déjà connus, et de nouveaux algorithmes pour le calcul du PGCD de deux polynômes de Ore et le calcul des résultants et sous-résultants de polynômes de Ore (ainsi que de polynômes usuels en généralisant au calcul des sous-résultants la formule déjà connue pour les résultants) en utilisant une matrice de multiplication à droite plus petite que la matrice de Sylvester utilisée habituellement.Ces résultats peuvent être réexploités indirectement dans le cryptosystème présenté par la suite bien que celui-ci ne soit pas basé sur les q-polynômes.• La partie suivante de notre travail est consacrée à l'introduction d'une nouvelle famille de codes en métrique rang appelés codes LRPC (pour Low Rank Parity Check codes). Ces codes ont la particularité d'avoir une matrice de parité de poids rang faible (et peuvent donc être vus comme une généralisation des codes LDPC ou MDPC à la métrique rang).Nous présentons le cryptosystème LRPC, un cryptosystème de type Mc Eliece en métrique rang basé sur les codes LRPC. Ces codes sont très peu structurés et sont donc vraisemblablement résistants aux attaques structurelles. La matrice de parité peut être choisie doublement circulante (on parle alors de codes DC-LRPC) ce qui diminue considérablement la taille de la clé.Ainsi, le cryptosystème DC-LRPC cumule les avantages d'offrir une bonne sécurité en étant basé sur un problème difficile (comme tous les cryptosystèmes basés sur les codes correcteurs), d'être faiblement structurés, de disposer d'une clé de taille assez petite (quelques milliers de bits au plus) et d'un algorithme de décodage efficace.Une attaque a été trouvée dans le cas du cryptosystème DC-LRPC. Cette attaque basée sur la notion de code replié permet de baisser significativement la sécurité du cryptosystème dans le cas où le polynôme X^(k-1)+X^(k-2)+⋯+1 est scindable (k désignant la dimension du code). Cependant ce n'est pas le cas pour les paramètres présentés où le cryptosystème reste valide. / The most commonly used encryption techniques in cryptography are based on problems in number theory. Despite their efficiency, they are vulnerable to post-quantum cryptographic attack. Therefore it is relevant to study other types of cryptosystems. In this work we study error-corrector codes based cryptosystmems, introduced by McEliece in 1978 ; being based on hard problems in coding theory, these cryptosystems do not have this weakness. However these cryptosystems are almost not used in practice because they are vulnerable to strucural attacks and they require a key with very big length. Recently a new family of codes named MDPC codes has been introduced as well as a cryptosystem that is based on these codes. It seems that MDPC codes are distinguishable only by finding words with weak weight in their dual, thus preventing them from structural attacks. Furthermore, they can have compact keys by using quasi-cyclic matrices.In the present paper we use the rank metric, a new metric for codes that was introduced by Gabidulin in and seems suited for a cryptographic use :• At first we studied Ore Polynomials and the special case of q-polynomials , the latter being iterates of the Fobenius automorphism on a finite field.These polynomials are widely in rank metric due to their use in the first code-based cryptosystems in rank metric. We reformulate already known results and give new results regarding the computation of GCD, resultants and subresultants of two Ore polynomials (as well as usual polynomials for which we give a generalization of the resultant computation to subresultants) using a right-hand multiplication matrix which is smaller than the well-known Sylvester matrix.These results may be reused in the cryptosystem we introduce in the next chapters, though this cryptosystem is not based on q-polynomials.• In the next part of our work we define the LRPC codes (for Low Rank Parity Check Codes), a new family of codes in rank metric. These codes have a parity check matrix whose rank weight is low (and thus they can be seen as a generalization of LDPC or MDPC codes to rank metric).We present the LRPC cryptosystem, a McEliece cryptosystem in rank metric based on LRPC codes. These codes are weakly structured and so are likely to resist structural attacks. We can choose a double-circulant parity check matrix which greatly lowers the key size (we name these particular codes DC-LRPC codes).Thus the DC-LRPC cryptosystems have a good security (being based on a hard problem in coding theory), are weakly structured, have small public keys and can be quickly decoded.An attack was found for DC-LRPC cryptosystem. This attack relies on folded codes and may greatly lower the security of the cryptosystem, however it works only when the polynomial X^(k-1)+X^(k-2)+⋯+1 has a divisor with big degree. We give parameters for which the cryptosystem remains valid.

La cryptographie prend une place de plus en plus importante dans la vie des sociétés depuis que ses utilisateurs se rendent compte de son importance pour sécuriser divers aspects de la vie, depuis les moyens de paiement, de communication et de sauvegarde des éléments de la vie privée des citoyens, jusqu'à la sécurité nationale des pays et de leurs armées. Depuis une vingtaine d'années on sait que les algorithmes de cryptographie ne doivent pas seulement être sûrs mathématiquement parlant, mais que leurs implémentations dans un dispositif les rendent vulnérables à d'autres menaces par des voies d'informations alternatives : les canaux auxiliaires. Que ce soit la consommation électrique, le temps ou les émissions électromagnétiques, ... ces biais ont été évalués et depuis leur découverte les recherches de nouvelles attaques et protections se succèdent afin de garantir la sécurité des algorithmes. La présente thèse s'inscrit dans ce processus et présente plusieurs travaux de recherche traitant d'attaques et de contre-mesures dans le domaine de l'exploitation de canaux auxiliaires et d'injections de fautes. Une première partie présente des contributions classiques où l'on cherche à retrouver une clef cryptographique lorsque la seconde s’attelle à un domaine moins étudié pour l'instant consistant à retrouver les spécifications d'un algorithme tenu secret. / Cryptography is taking an ever more important part in the life of societies since the users are realising the importance to secure the different aspects of life from citizens means of payment, communication and records of private life to the national securities and armies. During the last twenty years we learned that to mathematically secure cryptography algorithms is not enough because of the vulnerabilities brought by their implementations in a device through an alternative means to get information: side channels. Whether it is from power consumption, time or electromagnetic emissions ... those biases have been evaluated and, since their discovery, the researches of new attacks follow new countermeasures in order to guarantee security of algorithms. This thesis is part of this process and shows several research works about attacks and countermeasures in the fields of side channel and fault injections analysis. The first part is about classic contributions where an attacker wants to recover a secret key when the second part deals with the less studied field of secret specifications recovery.

Cette thèse porte sur les liens entre les codes correcteurs d'erreurs et les matrices de diffusion linéaires utilisées en cryptographie symétrique. L'objectif est d'étudier les constructions possibles de codes MDS additifs définis sur le groupe (Fm2, +) des m-uplets binaires et de minimiser le coût de l'implémentation matérielle ou logicielles de ces matrices de diffusion. Cette thèse commence par l'étude des codes définis sur un anneau de polynômes du type F[x]/f(x), qui généralisent les codes quasi-cycliques. Elle se poursuit par l'étude des codes additifs systématiques définis sur (Fm2, +) et leur lien avec la diffusion linéaire en cryptographie symétrique. Un point important de la thèse est l'introduction de codes à coefficient dans l'anneau des endomorphismes de Fm2. Le lien entre les codes qui sont des sous-modules à gauche et les codes additifs est mis en évidence. La dernière partie porte sur l'étude et la construction de matrices de diffusion MDS ayant de bonnes propriétés pour la cryptographie, à savoir les matrices circulantes, les matrices dyadiques, ainsi que les matrices ayant des représentations creuses minimisant leur implémentation. / This PhD focuses on the links between error correcting codes and diffusion matrices used in cryptography symmetric. The goal is to study the possible construction of additives MDS codes defined over the group (Fm2, +) of binary m-tuples and minimize cost of hardware or software implementation of these diffusion matrices. This thesis begins with the study of codes defined over the polynomial ring F[x]/f(x), these codes are a generalization of quasi-cyclic codes, and continues with the study of additive systematic codes over (Fm2, +) and there relation with linear diffusion on symmetric cryptography. An important point of this thesis is the introduction of codes with coefficients in the ring of endomorphisms of Fm2. The link between codes which are a left-submodules and additive codes have been identified. The last part focuses on the study and construction of efficient diffusion MDS matrices for the cryptographic applications, namely the circulantes matrices, dyadic matrices, and matrices with hollow representation, in ordre to minimize their implementations.