Depuis la publication en 1999 du papier fondateur de Paul C. Kocher, Joshua Jaffe et Benjamin Jun, intitulé "Differential Power Analysis", les attaques par canaux auxiliaires se sont révélées être un moyen d’attaque performant contre les algorithmes cryptographiques. En effet, il s’est avéré que l’utilisation d’information extraite de canaux auxiliaires comme le temps d’exécution, la consommation de courant ou les émanations électromagnétiques, pouvait être utilisée pour retrouver des clés secrètes. C’est dans ce contexte que cette thèse propose, dans un premier temps, de traiter le problème de la réduction de dimension. En effet, en vingt ans, la complexité ainsi que la taille des données extraites des canaux auxiliaires n’a cessé de croître. C’est pourquoi la réduction de dimension de ces données permet de réduire le temps et d’augmenter l’efficacité des attaques. Les méthodes de réduction de dimension proposées le sont pour des modèles de fuites complexe et de dimension quelconques. Dans un second temps, une méthode d’évaluation d’algorithmes logiciels est proposée. Celle-ci repose sur l’analyse de l’ensemble des données manipulées lors de l’exécution du logiciel évalué. La méthode proposée est composée de plusieurs fonctionnalités permettant d’accélérer et d’augmenter l’efficacité de l’analyse, notamment dans le contexte d’évaluation d’implémentation de cryptographie en boîte blanche. / Since the publication in 1999 of the seminal paper of Paul C. Kocher, Joshua Jaffe and Benjamin Jun, entitled "Differential Power Analysis", the side-channel attacks have been proved to be efficient ways to attack cryptographic algorithms. Indeed, it has been revealed that the usage of information extracted from the side-channels such as the execution time, the power consumption or the electromagnetic emanations could be used to recover secret keys. In this context, we propose first, to treat the problem of dimensionality reduction. Indeed, since twenty years, the complexity and the size of the data extracted from the side-channels do not stop to grow. That is why the reduction of these data decreases the time and increases the efficiency of these attacks. The dimension reduction is proposed for complex leakage models and any dimension. Second, a software leakage assessment methodology is proposed ; it is based on the analysis of all the manipulated data during the execution of the software. The proposed methodology provides features that speed-up and increase the efficiency of the analysis, especially in the case of white box cryptography.

La sécurité des applications sur le web est totalement dépendante de leur design et de la robustesse de l'implémentation des algorithmes et protocoles cryptographiques sur lesquels elles s'appuient. Cette thèse présente une nouvelle approche, applicable à de larges projets, pour vérifier l'état de l'art des algorithmes de calculs sur les grands nombres, tel que rencontrés dans les implémentations de référence. Le code et les preuves sont réalisés en F*, un langage orienté preuve et qui offre un système de types riche et expressif. L'implémentation et la vérification dans un langage d'ordre supérieur permet de maximiser le partage de code mais nuit aux performances. Nous proposons donc un nouveau langage, Low*, qui encapsule un sous ensemble de C en F* et qui compile vers C de façon sûre. Low* conserve toute l'expressivité de F* pour les spécifications et les preuves et nous l'utilisons pour implémenter de la cryptographie, en y intégrant les optimisations des implémentations de référence. Nous vérifions ce code en termes de sûreté mémoire, de correction fonctionnelle et d'indépendance des traces d'exécution vis à vis des données sensibles. Ainsi, nous présentons HACL*, une bibliothèque cryptographique autonome et entièrement vérifiée, dont les performances sont comparables sinon meilleures que celles du code C de référence. Plusieurs algorithmes de HACL* font maintenant partie de la bibliothèque NSS de Mozilla, utilisée notamment dans Firefox et dans RedHat. Nous appliquons les mêmes concepts sur miTLS, une implémentation de TLS vérifiée et montrons comment étendre cette méthodologie à des preuves cryptographiques, du parsing de message et une machine à état. / The security of Internet applications relies crucially on the secure design and robust implementations of cryptographic algorithms and protocols. This thesis presents a new, scalable and extensible approach for verifying state-of-the-art bignum algorithms, found in popular cryptographic implementations. Our code and proofs are written in F∗, a proof-oriented language which offers a very rich and expressive type system. The natural way of writing and verifying higher-order functional code in F∗ prioritizes code sharing and proof composition, but this results in low performance for cryptographic code. We propose a new language, Low∗, a fragment of F∗ which can be seen as a shallow embedding of C in F∗ and safely compiled to C code. Nonetheless, Low∗ retains the full expressiveness and verification power of the F∗ system, at the specification and proof level. We use Low∗ to implement cryptographic code, incorporating state-of-the-art optimizations from existing C libraries. We use F∗ to verify this code for functional correctness, memory safety and secret in- dependence. We present HACL∗, a full-fledged and fully verified cryptographic library which boasts performance on par, if not better, with the reference C code. Several algorithms from HACL∗ are now part of NSS, Mozilla’s cryptographic library, notably used in the Firefox web browser and the Red Hat operating system. Eventually, we apply our techniques to miTLS, a verified implementation of the Transport Layer Security protocol. We show how they extend to cryptographic proofs, state-machine implementations and message parsing verification.

En cryptographie classique, un algorithme de chiffrement est considéré comme une boîte noire, et un attaquant n'a accès qu'aux textes clairs et chiffrés. Mais un circuit cryptographique émet aussi des informations sensibles lors d'une opération cryptographique, comme sa consommation de courant ou ses émissions électro-magnétiques. Par conséquent, différentes techniques, appelées attaques par canaux auxiliaires, permettent d'exploiter ces fuites d'informations physiques pour casser des algorithmes cryptographiques avec une complexité très faible en comparaison avec les méthodes de la cryptanalyse classique. Dans ce travail, les attaques par canaux auxiliaires basées sur la consommation de courant ou les émissions électro-magnétiques sont d'abord étudiées d'un point de vue algorithmique, et différentes améliorations sont proposées. Ensuite, une attention particulière est consacrée à l'exploitation du canal auxiliaire électro-magnétique, et un flot de simulation des radiations magnétiques des circuits intégrés est proposé et validé sur deux microcontrôleurs. Finalement, certaines contremesures permettant de protéger les algorithmes de chiffrement contre ces menaces, basées sur des styles de logique équilibrées, sont présentées et évaluées. / In cryptography, a cipher is considered as a black-box, and an attacker has only access to plaintexts and ciphertexts. But a real world cryptographic device leaks additionnal sensitive informations during a cryptographic operation, such as power consumption or electro-magnetic radiations. As a result, several techniques, called Side-Channel Attacks, allow exploiting these physical leakages to break ciphers with a very low complexity in comparison with methods of classical cryptanalysis. In this work, power and electro-magnetic Side-Channel Attacks are firstly studied from an algorithmic point-of-view, and some improvements are proposed. Then, a particular attention is given on the exploitation of the electro-magnetic side-channel, and a simulation flow predicting magnetic radiations of ICs is proposed and validated on two microcontrollers. Finally, some countermeasures allowing to protect ciphers against these threats, based on balanced logic styles, are presented and evaluated.

Les systèmes de cryptographie à base de courbe elliptique (ECC) ont été adoptés comme des systèmes standardisés de cryptographie à clé publique (PKC) par l'IEEE, ANSI, NIST, SEC et WTLS. En comparaison avec la PKC traditionnelle, comme RSA et ElGamal, l'ECC offre le même niveau de sécurité avec des clés de plus petites tailles. Cela signifie des calculs plus rapides et une consommation d'énergie plus faible ainsi que des économies de mémoire et de bande passante. Par conséquent, ECC est devenue une technologie indispensable, plus populaire et considérée comme particulièrement adaptée à l'implémentation sur les dispositifs à ressources restreintes tels que les réseaux de capteurs sans fil (WSN). Le problème majeur avec les noeuds de capteurs chez les WSN, dès qu'il s'agit d'opérations cryptographiques, est les limitations de leurs ressources en termes de puissance, d'espace et de temps de réponse, ce qui limite la capacité du capteur à gérer les calculs supplémentaires nécessaires aux opérations cryptographiques. En outre, les mises en oeuvre actuelles de l'ECC sur WSN sont particulièrement vulnérables aux attaques par canaux auxiliaires (SCA), en particulier aux attaques par analyse de consommation (PAA), en raison de l'absence de la sécurité physique par blindage, leur déploiement dans les régions éloignées et le fait qu'elles soient laissées sans surveillance. Ainsi, les concepteurs de crypto-processeurs ECC sur WSN s'efforcent d'introduire des algorithmes et des architectures qui ne sont pas seulement résistants PAA, mais également efficaces sans aucun supplément en termes de temps, puissance et espace. Cette thèse présente plusieurs contributions dans le domaine des cryptoprocesseurs ECC conscientisés aux PAA, pour les dispositifs à ressources limitées comme le WSN. Premièrement, nous proposons deux architectures robustes et efficaces pour les ECC conscientisées au PAA. Ces architectures sont basées sur des algorithmes innovants qui assurent le fonctionnement de base des ECC et qui prévoient une sécurisation de l'ECC contre les PAA simples (SPA) sur les dispositifs à ressources limitées tels que les WSN. Deuxièmement, nous proposons deux architectures additionnelles qui prévoient une sécurisation des ECC contre les PAA différentiels (DPA). Troisièmement, un total de huit architectures qui incluent, en plus des quatre architectures citées ci-dessus pour SPA et DPA, deux autres architectures dérivées de l'architecture DPA conscientisée, ainsi que deux architectures PAA conscientisées. Les huit architectures proposées sont synthétisées en utilisant la technologie des réseaux de portes programmables in situ (FPGA). Quatrièmement, les huit architectures sont analysées et évaluées, et leurs performances comparées. En plus, une comparaison plus avancée effectuée sur le niveau de la complexité du coût (temps, puissance, et espace), fournit un cadre pour les concepteurs d'architecture pour sélectionner la conception la plus appropriée. Nos résultats montrent un avantage significatif de nos architectures proposées par rapport à la complexité du coût, en comparaison à d'autres solutions proposées récemment dans le domaine de la recherche.

Dans cette thèse, je propose des architectures de coprocesseurs haute performance pour implémenter les primitives de cryptographie asymétrique, comme le RSA, les courbes elliptiques ou le couplage. Les coprocesseurs décrits dans cette thèse ont été implémentés dans des FPGA, et présentent des performances jamais égalées auparavant dans la littérature publique sur ce type de technologie. La particularité de ces architectures est l'utilisation du Residue Number System, un mode de représentation alternatif qui utilise les restes chinois pour calculer efficacement les opérations arithmétiques sur les grands nombres. Ces travaux permettent de confirmer expérimentalement les avantages théoriques de ce mode de représentation pour l'arithmétique modulaire, issus de [14, 13, 43]. Au bénéfice théorique que le RNS apporte s'ajoute une forte capacité de parallélisation qui permet d'obtenir des designs réguliers et pipelinés, proposant une fréquence maximale importante tout en réalisant les opérations modulaires dans un nombre très faible de cycles, et ce quelle que soit la taille des nombres. A titre d'exemple, une multiplication scalaire sur une courbe de 160 bits s'effectue en 0.57 ms sur un Altera Stratix, et en 4 ms pour une courbe de 512 bits, là ou les techniques de représentation classiques réalisent la même opération en le double de temps, à technologie équivalente (excepté pour des courbes particulières). Dans le cas du couplage, le gain est encore plus intéressant, puisqu'il a permis une division par 4 de latence de la meilleure implémentation sur corps de grande caractéristique au moment de la publication de [35], et la première implémentation d'un couplage à 128 bits de sécurité sur corps de grande caractéristique à descendre en dessous de la milliseconde. Enfin, je démontre la capacité du RNS à sécuriser une implémentation haute performance, en proposant 2 contre-mesures contre les canaux auxiliaires et les fautes s'adaptant efficacement sur les coprocesseurs et pouvant être utilisées pour toutes les primitives cryptographiques basées sur l'arithmétique modulaire de grands nombres.

Les attaques par canaux auxiliaires sont les attaques les plus efficaces contre les systèmes cryptographiques. Alors que les attaques classiques n’exploitent que les entrées et sorties des algorithmes cryptographiques, les attaques par canaux auxiliaires utilisent également les fuites physiques du composant sous-jacent. Dans cette thèse, nous nous intéressons aux attaques par canaux auxiliaires qui exploitent la consommation de courant des composants pour retrouver les clefs secrètes. Ces attaques sont désignées par le terme attaques par analyse de courant. La majorité des attaques par analyse de courant existantes repose sur l’observation de variables dépendant uniquement de quelques bits de secret avec la stratégie diviser-pour-régner. Dans cette thèse, nous exhibons de nouvelles attaques qui exploitent l’observation de variables intermédiaires largement dépendantes de grands secrets. Notamment, nous montrons qu’en observant uniquement la fuite physique du résultat d’une multiplication de Galois entre une clef secrète de 128 bits et plusieurs messages connus, nous pouvons en déduire un système d’équations avec erreurs puis retrouver cette clef secrète. En parallèle, nous nous intéressons aux deux contre-mesures algorithmiques les plus répandues contre ces attaques par analyse de courant : les fonctions intrinsèquement résistantes aux fuites physiques et les schémas de masquage. Dans un premier temps, nous définissons un schéma de chiffrement résistant aux fuites physiques qui repose sur un rafraîchissement régulier de la clef secrète. Nous prouvons la sécurité de ce schéma dans le modèle de cryptographie résistante aux fuites (en anglais, leakage-resilient cryptography). Dans un second temps, nous construisons, à l’aide des méthodes formelles, un outil permettant de vérifier automatiquement la sécurité d’implémentations masquées. Nous exhibons également de nouvelles propriétés de sécurité, ainsi que des propriétés de composition qui nous permettent de générer une implémentation masquée à n’importe quel ordre à partir d’une implémentation non protégée. Finalement, nous présentons une étude de comparaison entre ces deux contre-mesures algorithmiques dans le but d’aider les experts industriels à déterminer la meilleure protection à intégrer dans leurs produits en fonction de leurs contraintes en termes de sécurité et de performances. / Side-channel attacks are the most efficient attacks against cryptosystems. While the classical blackbox attacks only exploit the inputs and outputs of cryptographic algorithms, side-channel attacks also get use of the physical leakage released by the underlying device during algorithms executions. In this thesis, we focus on one kind of side-channel attacks which exploits the power consumption of the underlying device to recover the algorithms secret keys. They are gathered under the term power-analysis attacks. Most of the existing power-analysis attacks rely on the observations of variables which only depend on a few secret bits using a divide-and-conquer strategy. In this thesis, we exhibit new kinds of attacks which exploit the observation of intermediate variables highly dependent on huge secrets. In particular, we show how to recover a 128-bit key by only recording the leakage of the Galois multiplication’s results between several known messages and this secret key. We also study two commonly used algorithmic countermeasures against side-channel attacks: leakage resilience and masking. On the one hand, we define a leakage-resilient encryption scheme based on a regular update of the secret key and we prove its security. On the other hand, we build, using formal methods, a tool to automatically verify the security of masked algorithms. We also exhibit new security and compositional properties which can be used to generate masked algorithms at any security order from their unprotected versions. Finally, we propose a comparison between these two countermeasures in order to help industrial experts to determine the best protection to integrate in their products, according to their constraints in terms of security and performances.

Dans cette thèse nous développons et améliorons des attaques de systèmes cryptographiques. Un nouvel algorithme de décomposition de signal appelé transformation de Hilbert-Huang a été adapté pour améliorer l’efficacité des attaques parcanaux auxiliaires. Cette technique permet de contrecarrer certaines contre-mesures telles que la permutation d’opérations ou l’ajout de bruit à la consommation de courant. La seconde contribution de ce travail est l’application de certaines distributions statistiques de poids de Hamming à l’attaque d’algorithmes de chiffrement par bloc tels que AES, DES ou LED. Ces distributions sont distinctes pour chaque valeur de sous-clef permettent donc de les utiliser comme modèles intrinsèques. Les poids de Hamming peuvent être découverts par des analyses de canaux auxiliaires sans que les clairs ni les chiffrés ne soient accessibles. Cette thèse montre que certaines contremesures peuvent parfois faciliter des attaques. Les contre-mesures contagieuses proposées pour RSA protègent contre les attaques par faute mais ce faisant et moyennant des calculs additionnels facilitent la découverte de la clef. Finalement, des contre-mesures à faible complexité calculatoire sont proposées. Elles sont basées sur le masquage antagoniste, c’est-à-dire, l’exécution d’une opération d’équilibrage sur des données sensibles pour masquer la consommation de courant. / The goal of the thesis is to develop and improve methods for defeating protected cryptosystems. A new signal decompositionalgorithm, called Hilbert Huang Transform, was adapted to increase the efficiency of side-channel attacks. This technique attempts to overcome hiding countermeasures, such as operation shuffling or the adding of noise to the power consumption. The second contribution of this work is the application of specific Hamming weight distributions of block cipher algorithms, including AES, DES, and LED. These distributions are distinct for each subkey value, thus they serve as intrinsic templates. Hamming weight data can be revealed by side-channel and fault attacks without plaintext and ciphertext. Therefore these distributions can be applied against implementations where plaintext and ciphertext are inaccessible. This thesis shows that some countermeasures serve for attacks. Certain infective RSA countermeasures should protect against single fault injection. However, additional computations facilitate key discovery. Finally, several lightweight countermeasures are proposed. The proposed countermeasures are based on the antagonist masking, which is an operation occurring when targeting data processing, to intelligently mask the overall power consumption.

Les systèmes de cryptographie à base de courbe elliptique (ECC) ont été adoptés comme des systèmes standardisés de cryptographie à clé publique (PKC) par l'IEEE, ANSI, NIST, SEC et WTLS. En comparaison avec la PKC traditionnelle, comme RSA et ElGamal, l'ECC offre le même niveau de sécurité avec des clés de plus petites tailles. Cela signifie des calculs plus rapides et une consommation d'énergie plus faible ainsi que des économies de mémoire et de bande passante. Par conséquent, ECC est devenue une technologie indispensable, plus populaire et considérée comme particulièrement adaptée à l’implémentation sur les dispositifs à ressources restreintes tels que les réseaux de capteurs sans fil (WSN). Le problème majeur avec les noeuds de capteurs chez les WSN, dès qu'il s'agit d’opérations cryptographiques, est les limitations de leurs ressources en termes de puissance, d'espace et de temps de réponse, ce qui limite la capacité du capteur à gérer les calculs supplémentaires nécessaires aux opérations cryptographiques. En outre, les mises en oeuvre actuelles de l’ECC sur WSN sont particulièrement vulnérables aux attaques par canaux auxiliaires (SCA), en particulier aux attaques par analyse de consommation (PAA), en raison de l'absence de la sécurité physique par blindage, leur déploiement dans les régions éloignées et le fait qu’elles soient laissées sans surveillance. Ainsi, les concepteurs de crypto-processeurs ECC sur WSN s'efforcent d'introduire des algorithmes et des architectures qui ne sont pas seulement résistants PAA, mais également efficaces sans aucun supplément en termes de temps, puissance et espace. Cette thèse présente plusieurs contributions dans le domaine des cryptoprocesseurs ECC conscientisés aux PAA, pour les dispositifs à ressources limitées comme le WSN. Premièrement, nous proposons deux architectures robustes et efficaces pour les ECC conscientisées au PAA. Ces architectures sont basées sur des algorithmes innovants qui assurent le fonctionnement de base des ECC et qui prévoient une sécurisation de l’ECC contre les PAA simples (SPA) sur les dispositifs à ressources limitées tels que les WSN. Deuxièmement, nous proposons deux architectures additionnelles qui prévoient une sécurisation des ECC contre les PAA différentiels (DPA). Troisièmement, un total de huit architectures qui incluent, en plus des quatre architectures citées ci-dessus pour SPA et DPA, deux autres architectures dérivées de l’architecture DPA conscientisée, ainsi que deux architectures PAA conscientisées. Les huit architectures proposées sont synthétisées en utilisant la technologie des réseaux de portes programmables in situ (FPGA). Quatrièmement, les huit architectures sont analysées et évaluées, et leurs performances comparées. En plus, une comparaison plus avancée effectuée sur le niveau de la complexité du coût (temps, puissance, et espace), fournit un cadre pour les concepteurs d'architecture pour sélectionner la conception la plus appropriée. Nos résultats montrent un avantage significatif de nos architectures proposées par rapport à la complexité du coût, en comparaison à d'autres solutions proposées récemment dans le domaine de la recherche. / Elliptic Curve Cryptosystems (ECC) have been adopted as a standardized Public Key Cryptosystems (PKC) by IEEE, ANSI, NIST, SEC and WTLS. In comparison to traditional PKC like RSA and ElGamal, ECC offer equivalent security with smaller key sizes, in less computation time, with lower power consumption, as well as memory and bandwidth savings. Therefore, ECC have become a vital technology, more popular and considered to be particularly suitable for implementation on resource constrained devices such as the Wireless Sensor Networks (WSN). Major problem with the sensor nodes in WSN as soon as it comes to cryptographic operations is their extreme constrained resources in terms of power, space, and time delay, which limit the sensor capability to handle the additional computations required by cryptographic operations. Moreover, the current ECC implementations in WSN are particularly vulnerable to Side Channel Analysis (SCA) attacks; in particularly to the Power Analysis Attacks (PAA), due to the lack of secure physical shielding, their deployment in remote regions and it is left unattended. Thus designers of ECC cryptoprocessors on WSN strive to introduce algorithms and architectures that are not only PAA resistant, but also efficient with no any extra cost in terms of power, time delay, and area. The contributions of this thesis to the domain of PAA aware elliptic curve cryptoprocessor for resource constrained devices are numerous. Firstly, we propose two robust and high efficient PAA aware elliptic curve cryptoprocessors architectures based on innovative algorithms for ECC core operation and envisioned at securing the elliptic curve cryptoprocessors against Simple Power Analysis (SPA) attacks on resource constrained devices such as the WSN. Secondly, we propose two additional architectures that are envisioned at securing the elliptic curve cryptoprocessors against Differential Power Analysis (DPA) attacks. Thirdly, a total of eight architectures which includes, in addition to the two SPA aware with the other two DPA awareproposed architectures, two more architectures derived from our DPA aware proposed once, along with two other similar PAA aware architectures. The eight proposed architectures are synthesized using Field Programmable Gate Array (FPGA) technology. Fourthly, the eight proposed architectures are analyzed and evaluated by comparing their performance results. In addition, a more advanced comparison, which is done on the cost complexity level (Area, Delay, and Power), provides a framework for the architecture designers to select the appropriate design. Our results show a significant advantage of our proposed architectures for cost complexity in comparison to the other latest proposed in the research field.

Les attaques par canaux auxiliaires sont apparues dans la deuxième moitié des années 1990. Ces attaques exploitent différentes informations qu’il est possible de collecter lors de l’exécution d’un algorithme sur un appareil cryptographique. Il est ainsi possible, entre autres, de mesurer la consommation d’énergie d’un appareil cryptographique, ou encore d’observer le temps d’exécution d’un certain algorithme sur un appareil. C’est à ces deux sources d’in- formation que nous nous intéressons dans ce travail. Après une présentation des concepts utiles à la lecture du travail et de l’état de l’art des attaques et des contre-mesures du domaine, nous abordons les résultats de nos recherches effectuées lors de ce travail de thèse. Nous présentons d’abord nos contributions aux attaques par mesure de consommation d’énergie :(1) une approche com- binant apprentissage semi-supervisé et attaques par templates pour retrouver le poids de Hamming des différents bytes d’une clé de chiffrement et (2) une approche utilisant des techniques d’apprentissage automatique pour attaquer une implantation protégée d’AES. Ensuite, nous abordons les contre-mesures investiguées durant nos recherches qui se résument (1) en la possibilité de rendre l’ordre des instructions d’AES le plus aléatoire possible en jouant sur la relation de dépendance entre celles-ci ainsi qu’en (2) l’étude de l’application partielle (sur un sous-ensemble de données) de certaines contre-mesures, afin de protéger les données sensibles d’un algorithme. Enfin, nous terminons ce travail par l’emploi de la programmation orientée aspects comme manière d’implanter des contre-mesures pour les attaques temporelles (sur RSA) et pour les attaques par mesures de consommation d’énergie (sur AES). / Doctorat en Sciences / info:eu-repo/semantics/nonPublished