Στη σύγχρονη ζωή του ανθρώπου η ανταλλαγή και η διακίνηση της πληροφορίας αποτελεί πλέον αναπόσπαστο κομμάτι. Η τεράστια ανάπτυξη των δικτύων υπολογιστών και η επικοινωνία πληροφοριών κάθε μορφής έφερε ένα τεράστιο πρόβλημα στην επιφάνεια, την ανάγκη για προστασία αυτής της πληροφορίας. Το πρόβλημα αυτό καλείται να το αντιμετωπίσει η επιστήμη της Κρυπτογραφίας όπου μέσα από διάφορους μετασχηματισμούς προσπαθεί θα μετατρέψει τα δεδομένα σε μια ακατανόητη μορφή η οποία θα είναι δυνατόν να αντιστραφεί μόνο από τον νόμιμο παραλήπτη. Για το λόγο αυτό έχουν αναπτυχθεί πληθώρα αλγορίθμων κρυπτογράφησης όπου παρόλο που η δουλειά τους είναι η ίδια, χειρίζονται και μετασχηματίζουν τα δεδομένα με διαφορετικό τρόπο. Στην παρούσα εργασία γίνεται παρουσίαση του αλγορίθμου AES (Advanced Encryption Standard) που αποτελεί το τρέχον πρότυπο από το NIST (National Institute of Standards and Technology). Ο AES ο οποίος είναι και γνωστός ως Rijndael, είναι ένας συμμετρικός αλγόριθμος τμήματος και βασίζεται στα δίκτυα μετάθεσης – αντικατάστασης, ενώ είναι υλοποιήσιμος και γρήγορος τόσο σε λογισμικό όσο και σε υλικό. Αντίθετα με τον προκάτοχο του DES, δεν χρησιμοποιεί το δίκτυο Feistel. Εφαρμόζεται σε έναν πίνακα Bytes 4x4 (128 bits), που ορίζεται ως κατάσταση (state), με τους περισσότερους μετασχηματισμούς να πραγματοποιούνται σε ένα πεπερασμένο πεδίο. Ο αλγόριθμος AES, δίνει τη δυνατότητα κρυπτογράφησης με τρία κλειδιά διαφορετικού μήκους, 128 bits κλειδί με 10 κύκλους επανάληψης, 192 bits κλειδί με 12 κύκλους επανάληψης και 256 bits κλειδί με 14 κύκλους επανάληψης παρουσιάζοντας κάθε φορά μεγάλη ανθεκτικότητα σε κρυπταναλυτικές επιθέσεις.Στα πλαίσια της εργασίας έγινε λεπτομερής ανάλυση των μετασχηματισμών που χρησιμοποιεί ο AES στην κρυπτογράφηση και αποκρυπτογράφηση σύμφωνα με το πρότυπο Fips-197 αρχικά σε θεωρητικό επίπεδο και έπειτα πραγματοποιήθηκαν υλοποιήσεις σε λογισμικό και σε υλικό. Συγκεκριμένα, στο 1ο κεφάλαιο της εργασίας γίνεται μια εισαγωγή στην Κρυπτογραφία, παρουσιάζοντας τις βασικές της έννοιες και την ιστορική της εξέλιξη από τα πρώτα χρόνια εμφάνισης της ως σήμερα. Στο κεφάλαιο 2, αρχικά παρουσιάζονται τα υπάρχοντα κρυπτοσυστήματα, αναδεικνύοντας κάθε φορά τον τρόπο με τον οποίο λειτουργούν, τους αλγόριθμους που υπάγονται σε αυτά και τις εφαρμογές που έχουν. Στη συνέχεια γίνεται σύγκριση μεταξύ των αλγορίθμων ενός συστήματος αλλά και μεταξύ των κρυπτοσυστημάτων. Το κεφάλαιο 3 αποτελεί το κυρίως σώμα της εργασίας καθώς σε αυτό παρουσιάζεται και επεξηγείται ο αλγόριθμος AES. Δίνεται το απαραίτητο μαθηματικό υπόβαθρο και αναλύονται οι μετασχηματισμοί του αλγορίθμου. Παρουσιάζεται ο τρόπος που επεκτείνονται τα κλειδιά του αλγορίθμου καθώς και οι διαδικασίες κρυπτογράφησης και αποκρυπτογράφησης. Τέλος γίνεται αναφορά σε ζητήματα ασφάλειας και στην αντοχή του AES σε κρυπταναλυτικές επιθέσεις, καθώς και στις εφαρμογές που χρησιμοποιείται. Στο 4ο κεφάλαιο παρουσιάζονται και συγκρίνονται οι μέθοδοι υλοποίησης του αλγορίθμου. Περιγράφεται μια υλοποίηση σε λογισμικό με τη χρήση της γλώσσας προγραμματισμού C++, η οποία επεκτείνεται και σε μια διαδικτυακή υλοποίηση και μια υλοποίηση σε υλικό με τη χρήση της περιγραφικής γλώσσας VHDL και το σχεδιαστικό εργαλείο Quartus II. Τέλος στο 5ο κεφάλαιο εξάγονται συμπεράσματα και γίνονται προτάσεις για μελλοντική εργασία. / In modern life the exchange and transfer of information has become an integral part. The enormous development of computer networks and the information communication of every form, has brought a new massive problem on the surface, the need to protect this information.The science of Cryptography is challenged to face this problem, so through various transformations is trying to convert tha data in a incomprehensive form, which will be possible to be inverted only from the legal receiver. For this reason a variety of algorithms have been developed and although their work is the same, they handle and convert data in different ways. In the present thesis the AES (Advanced Encryption Standard) algorithm is presented, which is the current standard of NIST (National Institute of Standards and Technology). AES, which is also known as Rijndael, is a symmetric block cipher and is based on substitution - permutation networks, while it can be efficiently implemented both in software and hardware. Unlike it's predecessor DES, it does not use Feistel network. It is applied in 4x4 Bytes matrix (128 bits), which is defined as state, with the most transformations to be performed in a finite field. AES algorithm provides encryption capability with three keys of different size: key of 128 bits with 10 rounds, key of 192 bits with 12 rounds and key of 256 bits with 14 rounds. This thesis includes detailed analysis of transformations that AES uses in ecryption and decryption according to the Fips-197 standard, along with software and hardware implementations. Specifically, in the first chapter an introduction to Cryptography is made, presenting basic concepts and a historical overview. In chapter 2, contemporary cryptosystems are introduced. In chapter 3 the AES algorithm is presented and explained. The necessary mathematical background is provided and the transformations of the algorithm are analysed. The way the algorithm keys are expanded is presented, as well as the encryption and decryption processes. In chapter 4 the implementations of AES are presented and compared. An implementation in software is described using the programming language C++, and an implementation in hardware is given using the VHDL language and the design tool Altera Quartus II. Finally in chapter 5 the conclusions are given and proposals are made for future work.

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.

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.

La stéganographie numérique est une technique récente qui a émergé comme une source importante pour la sécurité des données. Elle consiste à envoyer secrètement et de manière fiable des informations dissimulées et non pas seulement à masquer leur présence. Elle exploite les caractéristiques des fichiers médias numériques anodins, tels que l’image, le son et la vidéo,et les utilise comme support pour véhiculer des informations secrète d’une façon inaperçue. Les techniques de cryptage et de tatouage sont déjà utilisées pour résoudre les problèmes liés à la sécurité des données. Toutefois,l’évolution des tentatives d’interception et de déchiffrement des données numériques nécessitent de nouvelles techniques pour enrayer les tentatives malveillantes et d’élargir le champ des applications y associées. L’objectif principal des systèmes stéganographiques consiste à fournir de nouveaux moyens sécurisés, indétectables et imperceptibles pour dissimuler des données.La stéganographie est utilisée sous l’hypothèse qu’elle ne sera pas détectée si personne n’essaye de la découvrir. Les techniques récentes destéganographie ont déjà été employées dans diverses applications. La majorité de ces applications ont pour objectif d’assurer la confidentialité des données.D’autres par contre sont utilisées malicieusement. L’utilisation de la stéganographie à des fins criminelles, de terrorisme, d’espionnage ou de piraterie constitue une menace réelle. Ces tentatives malveillantes de communiquer secrètement ont récemment conduit les chercheurs à inclure une nouvelle branche de recherche: la stéganalyse, pour contrer les techniques stéganographique. L’objectif principal de la stéganalyse est de détecter la résence potentielle d’un message dissimulé dans un support numérique et ne considère pas nécessairement son extraction. La parole numérique constitue un terrain de prédilection pour dissimuler des données numériques. En effet, elle est présente en abondance grâce aux technologies de télécommunications fixes ou mobiles et aussi à travers divers moyens de stockage de l’audio numérique. Cette thèse étudie la stéganographie et la stéganalyse utilisant la voix numérisée comme support et vise à (1) présenter un algorithme qui répond aux exigences des systèmes stéganographiques reliées à la capacité élevée, l’indétectabilité et l’imperceptibilité des données dissimulées, (2) le contrôle de la distorsion induite par le processus de dissimulation des données (3) définir un nouveau concept de zones spectrales dans le domaine de Fourier utilisant et l’amplitude et la phase (4) introduire un nouveau algorithme de stéganalyse basé sur les techniques de compression sans pertes d’information à la fois simple et efficace. La performance de l’algorithme stéganographique est mesurée par des méthodes d’évaluation perceptuelles et statistiques. D’autre part, la performance de l’algorithme de stéganalyse est mesurée par la capacité du système à distinguer entre un signal audio pur et un signal audio stéganographié. Les résultats sont très prometteurs et montrent des compromis de performance intéressants par rapport aux méthodes connexes. Les travaux futurs incluent essentiellement le renforcement de l’algorithme de stéganalyse pour qu’il soit en mesure de détecter une faible quantité de données dissimulées. Nous planifions également l’intégration de notre algorithme de stéganographie dans certaines plateformes émergentes telles que l’iPhone. D’autres perspectives consistent à améliorer l’algorithme stéganographique pour que les données dissimulées soit résistantes au codage de la parole, au bruit et à la distorsion induits parles canaux de transmission. / Digital steganography is a young flourishing science emerged as a prominent source of data security. The primary goal of steganography is to reliably send hidden information secretly, not merely to obscure its presence. It exploits the characteristics of digital media files such as: image, audio, video, text by utilizing them as carriers to secretly communicate data. Encryption and watermarking techniques are already used to address concerns related to datasecurity. However, constantly-changing attacks on the integrity of digital data require new techniques to break the cycle of malicious attempts and expand the scope of involved applications. The main objective of steganographic systems is to provide secure, undetectable and imperceptible ways to conceal high-rate of data into digital medium. Steganography is used under the assumption that it will not be detected if no one is attempting to uncover it. Steganography techniques have found their way into various and versatile applications. Some of these applications are used for the benefit of people others are used maliciously. The threat posed by criminals, hackers, terrorists and spies using steganography is indeed real. To defeat malicious attempts when communicating secretly, researchers’ work has been lately extended toinclude a new and parallel research branch to countermeasure steganagraphy techniques called steganalysis. The main purpose of steganalysis technique is to detect the presence or not of hidden message and does not consider necessarily its successful extraction. Digital speech, in particular, constitutes a prominent source of data-hiding across novel telecommunication technologies such as covered voice-over-IP, audio conferencing, etc. This thesis investigatesdigital speech steganography and steganalysis and aims at: (1) presenting an algorithm that meets high data capacity, undetectability and imperceptibility requirements of steganographic systems, (2) controlling the distortion induced by the embedding process (3) presenting new concepts of spectral embedding areas in the Fourier domain which is applicable to magnitude and phase spectrums and (4) introducing a simple yet effective speech steganalysis algorithm based on lossless data compression techniques. The steganographic algorithm’s performance is measured by perceptual and statistical evaluation methods. On the other hand, the steganalysis algorithm’s performance is measured by how well the system can distinguish between stego- and cover-audio signals. The results are very promising and show interesting performance tradeoffs compared to related methods. Future work is based mainly on strengthening the proposed steganalysis algorithm to be able to detect small hiding capacity. As for our steganographic algorithm, we aim at integrating our steganographic in some emerging devices such as iPhone and further enhancing the capabilities of our steganographic algorithm to ensure hidden-data integrity under severe compression, noise and channel distortion.

Tout d’abord, mon sujet de recherche porte sur le cryptographie à clé publique, plus précisément la cryptographie basée sur la théorie des codes correcteurs d’erreurs. L’objectif principal de cette thèse est d’analyser la sécurité des systèmes de chiffrement. Pour cela j’étudie les propriétés structurelles des différentes familles de codes linéaires utilisées dans la pratique. Mon travail de recherche s’est orienté de maniéré naturelle, vers l’étude des deux dernières propositions de cryptosystèmes, plus exactement le schéma de McEliece à base des codes MDPC [MTSB13](moderate parity check codes) et des codes Polaires [SK14]. Dans le cas des codes MDPC on a mis en évidence une faiblesse importante au niveau des clés utilisées par les utilisateurs du système. En effet, on a proposé un algorithme très efficace qui permet de retrouver une clé privé à partir d’une clé publique. Ensuite on a compté le nombre des clés faibles et on a utilisé le problème d’équivalence de codes pour élargir le nombre de clés faibles. On a publié notre travail de recherche dans une conférence internationale en cryptographie [BDLO16]. Ensuite on a étudié les codes Polaires et leur application à la cryptographie à clé publique. Depuis leur découverte par E. Arikan [Arı09], les codes Polaires font partie des famille de codes les plus étudié du point de vue de le théorie de l’information. Ce sont des codes très efficaces en terme de performance car ils atteignent la capacité des canaux binaires symétriques et ils admettent des algorithmes d’encodage et décodage très rapides. Néanmoins, peu des choses sont connu sur leur propriétés structurelles. Dans ce cadre la, on a introduit un formalisme algébrique qui nous a permit de révéler unegrande partie de la structure de ces codes. En effet, on a réussi à répondre à des questions fondamentales concernant les codes Polaires comme : le dual ou la distance minimale d’un code Polaire, le groupe des permutations ou le nombre des mots de poids faible d’un code Polaire. On a publié nos résultats dans une conférence internationale en théorie de l’information [BDOT16]. Par la suite on a réussi à faire une cryptanalyse complète du schéma de McEliece à base des codes Polaires. Ce résultat a été une application directe des propriétés découvertes sur les codes Polaires et il a été publié dans une conférence internationale en cryptographie post-quantique [BCD+16]. / First of all, during my PhD I focused on the public key cryptography, more exactly on the code-based cryptography. The main motivation is to study the security of the latest encryption schemes. For that, I analyzed in detail the structural properties of the main code families. Thus, my research was naturally directed to the study of the McEliece based encryption schemes, among which the latest MDCP based variant [MTSB13] and Polar codes variant [SK14]. In the case of the MDPC based variant, we manage to reveal an important weakness regarding the key pairs that are used in the protocol. Indeed, we proposed an efficient algorithm that retrieves the private key given the public key of the scheme. Next we counted the proportion of weak keys and we used the code equivalence problem to extend the number of weak keys. We published our results in an international conference in cryptography [BDLO16]. Next we studied the Polar codes and their application to public key cryptography.Since they were discovered by Arikan [Arı09], Polar codes are part of the most studied from an information theory point of view, family of codes. In terms of performance they are really efficient since they are capacity achieving over the Binary Discrete Memoryless Channels and they allow extremely fast encoding and decoding algorithms. Nonetheless, few facts are known about their structure. In this context, we have introduced an algebraic formalism which allowed us to reveal a big part of the structure of Polar codes. Indeed, we have managed to answer fundamental questions regarding Polar codes such as the dual, the minimum distance, the permutation group and the number of minimum weight codewords of a Polar code. Our results were published in an international conference in information theory [BDOT16]. We also managed to completely cryptanalyze the McEliece variant using Polar codes. The attack was a direct application of the aforementioned results on the structural properties of Polar codes and it was published in an international conference in postquantum cryptography [BCD+16].

Le sujet de cette thèse est l'analyse de sécurité des implantations cryptographiques embarquées.La sécurité a toujours été un besoin primaire pour les communications stratégiques et diplomatiques dans l'histoire. Le rôle de la cryptologie a donc été de fournir les réponses aux problèmes de sécurité, et le recours à la cryptanalyse a souvent permis de récupérer le contenu des communications des adversaires.L'arrivée des ordinateurs a causé un profond changement des paradigmes de communication et aujourd'hui le besoin de sécuriser les communications ne s'étend qu’aux échanges commerciaux et économiques.La cryptologie moderne offre donc les solutions pour atteindre ces nouveaux objectifs de sécurité, mais ouvre la voie à des nouvelles attaques : c'est par exemple le cas des attaques par fautes et par canaux auxiliaires, qui représentent aujourd'hui les dangers plus importants pour les implantations embarquées.Cette thèse résume le travail de recherche réalisé ces trois dernières années dans le rôle d'ingénieur en sécurité au sein d'Oberthur Technologies. La plupart des résultats a été publiée sous forme d'articles de recherche [9,13-17] ou de brevets [1-6].Les objectifs de recherche en sécurité pour les entreprises du milieu de la sécurité embarqué sont doubles. L'ingénieur en sécurité doit montrer la capacité d'évaluer correctement la sécurité des algorithmes et de mettre en avant les possibles dangers futurs. Par ailleurs il est désirable de découvrir des nouvelles techniques de défense qui permettent d'obtenir un avantage sur les concurrents. C'est dans ce contexte que ce travail est présenté.Ce manuscrit est divisé en quatre chapitres principaux.Le premier chapitre présente une introduction aux outils mathématiques et formels nécessaires pour comprendre la suite. Des résultats et notions fondamentaux de la théorie de l'information, de la complexité, et des probabilités sont présentés, ainsi qu'une introduction à l'architecture des micro-ordinateurs.Le chapitre suivant présente la notion d'attaque par faute et des stratégies connues pour contrecarrer ce type d'attaques. Le corps du deuxième chapitre est ensuite dédié à notre travail sur le code infectif pour les algorithmes symétriques et asymétriques [15-17] ainsi que à notre travail sur les attaques par faute sur courbes elliptiques [13].Le troisième chapitre est dédié aux attaques par canaux auxiliaires, et présente une introduction aux résultats et à certaines attaques et contremesures classiques du domaine. Ensuite nos deux nouvelles attaques ciblant des contremesures considérées sécurisées sont présentées [9,14]. Dans ce troisième chapitre est enfin présentée notre nouvelle attaque combinée qui permet de casser des implémentations sécurisées à l'état de l'art.A la fin de ce manuscrit, le quatrième chapitre présente les conclusions de notre travail, ainsi que des perspectives pour des nouveaux sujets de recherche.Pendant nos investigations nous avons trouvé différentes contremesures qui permettent de contrecarrer certaines attaques.Ces contremesures ont été publiées sous la forme de brevets [1-6]. Dans certains cas les contremesures sont présentées avec l'attaque qu'elles contrecarrent. / The subject of this thesis is the security analysis of cryptographic implementations. The need for secure communications has always been a primary need for diplomatic and strategic communications. Cryptography has always been used to answer this need and cryptanalysis have often been solicited to reveal the content of adversaries secret communications. The advent of the computer era caused a shift in the communication paradigms and nowadays the need for secure communications extends to most of commercial and economical exchanges. Modern cryptography provides solutions to achieve such new security goals but also open the way to a number of new threats. It is the case of fault and side-channel-attacks, which today represents the most dangerous threats for embedded cryptographic implementations. This thesis resumes the work of research done during the last years as a security engineer at Oberthur Technologies. Most of the results obtained have been published as research papers [9,13-17] or patents [1-6]. The security research goals of companies around the world working in the embedded domain are twofold. The security engineer has to demonstrate the ability to correctly evaluate the security of algorithms and to highlight possible threats that the product may incur during its lifetime. Furthermore it is desirable to discover new techniques that may provide advantages against competitors. It is in this context that we present our work.This manuscript is divided into four main chapters.The first chapter presents an introduction to various mathematical and computational aspects of cryptography and information theory. We also provide an introduction to the main aspects of the architecture of secure micro-controllers.Afterwards the second chapter introduces the notion of fault attacks and presents some known attack and countermeasure [15-17]. We then detail our work on asymmetric and symmetric infective fault countermeasures as long as on elliptic curves fault attacks [13].The third chapter discusses about side-channels, providing a brief introduction to the subject and to well-known side-channel attacks and countermeasures. We then present two new attacks on implementations that have been considered secure against side channels [9,14]. Afterwards we discuss our combined attack which breaks a state-of-the-art secure implementation [10].Finally, the fourth chapter concludes this works and presents some perspectives for further research.During our investigations we have also found many countermeasures that can be used to thwart attacks. These countermeasures have been mainly published in the form of patents [1-6]. Where possible some of them are presented along with the attack they are conceived to thwart.

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

Les schémas de Chiffrement Complètement Homomorphe (FHE) permettent de manipuler des données chiffrées avec grande flexibilité : ils rendent possible l'évaluation de fonctions à travers les couches de chiffrement. Depuis la découverte du premier schéma FHE en 2009 par Craig Gentry, maintes recherches ont été effectuées pour améliorer l'efficacité, atteindre des nouveaux niveaux de sécurité, et trouver des applications et liens avec d'autres domaines de la cryptographie. Dans cette thèse, nous avons étudié en détail ce type de schémas. Nos contributions font état d'une nouvelle attaque de récuperation des clés au premier schéma FHE, et d'une nouvelle notion de sécurité en structures hierarchiques, évitant une forme de trahison entre les usagers tout en gardant la flexibilité FHE. Enfin, on décrit aussi des implémentations informatiques. Cette recherche a été effectuée au sein du Laboratoire de Mathématiques de Versailles avec le Prof. Louis Goubin. / Fully Homomorphic Encryption schemes allow public processing of encrypted data. Since the groundbreaking discovery of the first FHE scheme in 2009 by Craig Gentry, an impressive amount of research has been conducted to improve efficiency, achieve new levels of security, and describe real applications and connections to other areas of cryptography. In this Dissertation, we first give a detailed account on research these past years. Our contributions include a key-recovery attack on the ideal lattices FHE scheme and a new conception of hierarchic encryption, avoiding at some extent betrayal between users while maintaining the flexibility of FHE. We also describe some implementations. This research was done in the Laboratoire de Mathématiques de Versailles, under supervision of Prof. Louis Goubin.

Από τότε που ολοένα και περισσότερα εμπιστευτικά δεδομένα ανταλλάσσονται με ηλεκτρονικό τρόπο η ανάγκη για προστασία των δεδομένων αυτών γίνεται ολοένα και μεγαλύτερη. Στις πραγματικές εφαρμογές όπου χρησιμοποιούνται συστήματα κρυπτογραφίας παρατηρούνται νέες τεχνικές επίθεσης πέρα από αυτές που στηρίζονται στην μαθηματική ανάλυση. Εφαρμογές τόσο σε υλικό όσο και σε λογισμικό, παρουσιάζουν ένα αχανές πεδίο από επιθέσεις. Οι Side-Channel-Attacks εκμεταλλεύονται πληροφορίες που διαρρέουν από μια συσκευή κρυπτογράφησης. Μάλιστα από την μέρα που εμφανίστηκε μία συγκεκριμένη μέθοδος επίθεσης, προσελκύει ολοένα και μεγαλύτερο ενδιαφέρον. Πρόκειται για την Διαφορική Ανάλυση Ισχύος (Differential Power Analysis (DPA)) που πρωτοπαρουσιάστηκε από την Cryptography Research. Η DPA χρησιμοποιεί την πληροφορία που διαρρέει από μια συσκευή κρυπτογράφησης, και πρόκειται για την κατανάλωση ισχύος. Μία λιγότερο δυνατή παραλλαγή της DPA είναι η Simple Power Analysis (SPA), που παρουσιάστηκε επίσης από την Cryptography Research. Βασικός στόχος της DPA είναι να μετρηθεί με ακρίβεια η κατανάλωση ισχύος του συστήματος. Έπειτα απαιτείται η γνώση του αλγόριθμου που εκτελείται από την συσκευή, ενώ τέλος απαραίτητο είναι ένα σύνολο από γνωστά κρυπτογραφήματα ή αυθεντικά μηνύματα. Η στρατηγική της επίθεσης απαιτεί την μέτρηση πολλών δειγμάτων και στην συνέχεια την διαίρεσή τους σε δύο ή περισσότερα σύνολα με βάση ενός κανόνα . Εν συνεχεία στατιστικές μέθοδοι χρησιμοποιούνται για την επιβεβαίωση του κανόνα αυτού. Αν και μόνο αν ο κανόνας αυτός είναι σωστός τότε μπορούμε να παρατηρήσουμε αξιοπρόσεκτες τιμές στην στατιστική ανάλυση. Σκοπός της εργασίας αυτής είναι να καθορίσουμε με περισσότερες λεπτομέρειες την DPA, να αναπτύξουμε ένα περιβάλλον που θα πραγματοποιεί την επίθεση αυτή, σε μια υλοποίηση του DES (Data Encryption Standard) αλγόριθμου κρυπτογράφησης με την χρήση FPGA Board και να γίνει πειραματική εκτίμηση. / -

Στη παρούσα διδακτορική διατριβή του κ. Χαράλαμπου Μιχαήλ με τίτλο «Βελτιστοποίηση Επαναπροσδιοριζόμενων Αρχιτεκτονικών για Απόδοση και Κατανάλωση Ενέργειας για Κρυπτογραφικές Εφαρμογές και Εφαρμογές Κυριαρχούμενες από Δεδομένα» προτείνονται, αναπτύσσονται και μελετώνται αποδοτικές τεχνικές βελτιστοποίησης της απόδοσης ή/και της κατανάλωσης ενέργειας για κρυπτογραφικές εφαρμογές καθώς και εφαρμογές κυριαρχούμενες από δεδομένα που υλοποιούνται σε ενσωματωμένες πλατφόρμες ειδικού σκοπού. Συνολικά, οι προτεινόμενες τεχνικές μελετήθηκαν για τις διάφορες παραμέτρους που έχουν και συνολικά οδήγησαν στην διαμόρφωση της προτεινόμενης γενικής μεθοδολογίας βελτιστοποίησης των κρυπτογραφικών και λοιπών εφαρμογών κυριαρχούμενων από δεδομένα. Τα θεωρούμενα συστήματα στοχεύουν σε αριθμητικά απαιτητικές εφαρμογές και προέκυψαν εντυπωσιακές βελτιστοποιήσεις ειδικά δε στην απόδοση συγκεκριμένων κρυπτογραφικών εφαρμογών όπως οι συναρτήσεις κατακερματισμού και ανάμειξης (hash functions) και κατά συνέπεια και των αντίστοιχων κρυπτογραφιών μηχανισμών στους οποίους αυτές χρησιμοποιούνται. Πρωταρχικός σχεδιαστικός στόχος είναι η αύξηση της ρυθμαπόδοσης σχεδιάζοντας κρυπτογραφικές εφαρμογές για διακομιστές υπηρεσιών ή γενικότερα εφαρμογές κυριαρχούμενες από δεδομένα. Λαμβάνοντας επίσης υπόψη το γεγονός ότι η κρυπτογραφία αποτελεί σήμερα –πιο πολύ παρά ποτέ- ένα αναγκαίο και αναντικατάστατο συστατικό της ανάπτυξης ηλεκτρονικών υπηρεσιών μέσω διαδικτύου και της εν τέλει μετάβασης της ανθρωπότητας στο νέο οικονομικό μοντέλο της «ηλεκτρονικής οικονομίας» είναι προφανής η σημασία της προτεινόμενης μεθοδολογίας και των αντίστοιχων σχεδιασμών που προκύπτουν. Η ολοκλήρωση των κρυπτογραφικών συστημάτων ασφαλείας σε υλικό είναι σχεδόν αναγκαία για τα ενσωματωμένα συστήματα κρυπτογράφησης. Τα πλεονεκτήματα που έχουμε είναι η υψηλή απόδοση, η μειωμένη κατανάλωση ισχύος με μειονέκτημα το κόστος της ολοκλήρωσης σε υλικό. Νέες τεχνολογίες όπως FPGAs (Field-Programmable Gate Array), επιτρέπουν την πιο εύκολη ολοκλήρωση του αλγορίθμου και την ανανέωση - αντικατάστασή του από νεώτερους-βελτιωμένους. Ήδη τα τελευταίας γενιάς FPGAs τείνουν να έχουν τις ιδιότητες των ASICs (Application-Specific Integrated Circuit) -μειωμένη κατανάλωση ισχύος, υψηλή απόδοση, και ρύθμιση της λειτουργικότητας ανάλογα την εφαρμογή. Ένα άλλο πλεονέκτημα των υλοποιήσεων σε υλικό είναι πως από την φύση τους είναι λιγότερο ευαίσθητο σε επιθέσεις κρυπτανάλυσης ενώ μπορούν ευκολότερα να ενσωματώσουν πολιτικές αντιμετώπισης κρυπταναλυτικών τεχνικών . Ερευνητική Συνεισφορά Ανάπτυξη και μελέτη τεχνικών βελτιστοποίησης που οδηγούν σε σχέδια με πολύ υψηλή ρυθμαπόδοση και περιορισμένο κόστος σε επιφάνεια ολοκλήρωσης για κρυπτογραφικές και υπολογιστικά απαιτητικές εφαρμογές Αναπτύσσονται και αναλύονται όλες οι επιμέρους τεχνικές που αξιολογήθηκαν κατά την εκπόνηση της εν λόγω διδακτορικής διατριβής και χρησιμοποιούνται για την βελτιστοποίηση των σχεδίων σε υλικό. Μελετώνται οι παράμετροι εφαρμογής ανάλογα με την υφή της κάθε τεχνικής και τα τιθέμενα σχεδιαστικά κριτήρια, τα οποία εξαρτώνται από τα επιθυμητά χαρακτηριστικά των σχεδίων σε υλικό καθώς και από τις εν γένει προδιαγραφές τους ανάλογα με τον εκάστοτε σχεδιαστικό στόχο. Ανάπτυξη και μελέτη «πάνω-προς-τα-κάτω» μεθοδολογίας βελτιστοποίησης των σχεδίων που οδηγούν σε πολύ υψηλή ρυθμαπόδοση και περιορισμένο κόστος σε επιφάνεια ολοκλήρωσης για κρυπτογραφικές και υπολογιστικά απαιτητικές εφαρμογές Αναπτύσσεται ολοκληρωμένη και δομημένη συνολική μεθοδολογία βελτιστοποίησης σχεδίων, με βάση τις επιμέρους τεχνικές που παρουσιάστηκαν και αναλύθηκαν, που οδηγεί σε γενική μεθοδολογία η οποία είναι εφαρμόσιμη σε όλες σχεδόν τις συναρτήσεις κατακερματισμού για τις οποίες καταφέρνει να παράγει σχέδια υψηλής απόδοσης με περιορισμένο κόστος σε επιφάνεια ολοκλήρωσης. Ταυτόχρονα, αναλύονται τα θεωρητικώς αναμενόμενα οφέλη από την κάθε επιμέρους τεχνική βελτιστοποίησης καθώς και από την συνολική εφαρμογή της μεθοδολογίας βελτιστοποίησης του σχεδιασμού σε υλικό ανάλογα με την επιλεχθείσα τιμή των παραμέτρων της κάθε εφαρμοζόμενης τεχνικής. Ανάπτυξη σχεδίων σε υλικό πολύ υψηλής βελτιστοποίησης για τις συναρτήσεις κατακερματισμού SHA-1 και SHA-256 Παρουσιάζεται η διαδικασία βελτιστοποίησης του σχεδιασμού σε υλικό των δυο πιο σημαντικών συναρτήσεων κατακερματισμού αναφέροντας σε κάθε περίπτωση τα επιμέρους κέρδη, καθώς και την συνολική βελτίωση που επιτεύχθηκε με την εφαρμογή της προτεινόμενης μεθοδολογίας. Οι δύο συναρτήσεις είναι οι SHA-1 (η πιο δημοφιλής συνάρτηση κατακερματισμού στις σημερινές εφαρμογές) και SHA-256 (που αναμένεται να χρησιμοποιηθεί ευρύτατα στο μέλλον παρέχοντας υψηλότερο επίπεδο ασφάλειας). Υλοποιήσεις σε συγκεκριμένες επαναπροσδιοριζόμενες αρχιτεκτονικές συγκρίνονται με αντίστοιχες που έχουν προταθεί ερευνητικά ή είναι εμπορικά διαθέσιμες, αποδεικνύωντας την υπεροχή των προτεινόμενων σχεδίων. Έτσι προκύπτουν σχέδια πολύ υψηλής ρυθμαπόδοσης (τουλάχιστον 160% βελτιωμένοι σε σχέση με συμβατικές υλοποιήσεις) με περιορισμένο κόστος σε επιφάνεια ολοκλήρωσης (λιγότερο από 10% σε επίπεδο συνολικού κρυπτογραφικού συστήματος στην χειρότερη περίπτωση σε σχέση με συμβατικές υλοποιήσεις), βελτιστοποιώντας τον σχεδιαστικό παράγοντα «απόδοση x επιφάνεια ολοκλήρωσης» σε σχέση με άλλες εμπορικές ή ακαδημαϊκές υλοποιήσεις. / In this Ph.D dissertation, certain design techniques and methodologies, for various hardware platforms, aiming to boost performance of cryptographic modules and data intensive applications are presented. This way we manage to obtain hardware designs with extremely high throughput performing much better that anyone else that has been previously proposed either by academia or industry. Taking in consideration the rapid evolution of e-commerce and the need to secure all kind of electronic transactions, it is obvious that there is a great need to achieve much higher throughputs for certain cryptographic primitives. Especially in IPv6, HMAC etc it is crucial to design hash functions that achieve the highest degree of throughput since hashing is the limiting factor in such security schemes. The proposed methodology achieves to tackle this problem achieving to offer design solutions for hashing cores that can increase their throughput up to 160%. The proposed methodology is generally applicable to all kind of hash functions and this is a main characteristic of its importance. The proposed techniques and methodologies go far beyond from just unrolling the rounds of the algorithm and/or using extended pipelining techniques. It offers an analysis on these techniques while at the same time proposes some new, which all together form a holistic methodology for designing high-throughput hardware implementations for hash functions or other data intensive applications. These designs that can achieve high throughput rates are appropriate for high-end applications that are not constrained in power consumption and chip covered area. The main contributions of this PhD thesis involve: Developing and study of certain optimizing techniques for increasing throughput in cryptographic primitives and data intensive applications Certain design techniques that can take part in a generic methodology for improving hardware performance characteristics are proposed and studied. This study has been conducted in terms of each technique’s parameters and certain design criteria are mentioned in order to choose their values. These design criteria depend on the intended hardware characteristics, specifications and available hardware resources for the cryptographic primitive or data intensive application. Developing and study of top-down methodology for increasing throughput in cryptographic primitives and data intensive applications Techniques that were previously proposed and analyzed are merged in order to form propose a top-down methodology able to boost performance of cryptographic primitives and data intensive applications. Design parameters are studied in order to propose various design options with the default one being achieving the highest degree of throughput maintaining the best throughput/area ratio. The proposed methodology can significantly increase throughput of hardware designs leading theoretically even to 160% increase of throughput with less than 10% cost in integration area for the whole cryptographic system. Highly optimized hardware designs for the two main hash functions: SHA-1 and SHA-256 with high-throughput properties. In this contribution high throughput designs and implementations are proposed concerning the two most widely used hash functions SHA-1 and SHA-256. SHA-1 is currently the most widely deployed hashing function whereas SHA-256 has started to phase out SHA-1 due to security issues that have recently been reported. These two designs also serve as case studies for the application of the proposed methodology aiming to increase throughput in cryptographic modules and data intensive applications. Our implementation does not only increases throughput by a large degree, but it also utilizes limited area resources thus offering an advantageous "throughput x area" product in comparison with other hashing cores implementations, proposed either by academia or industry. The proposed design achieves maximum throughput over 4.7 Gbps for SHA-1 and over 4.4 Gbps for SHA-256 in Xilinx Virtex II platform with minor area penalty comparing to conventional implementations. These synthesis results are only slightly decreased after the place-and-route procedure