Search

Noise in digital circuits has always been minimized to achieve high signal integrity, robust operation and of course high performance. However, for cryptographic applications, increased noise can in fact be beneficial. It can be used effectively to reduce the SNR and to make it harder for an adversary to extract useful information (secret keys) from the side channel leakage data. A natural question concerns the extent to which intrinsic MOSFET noise is required to improve security. In this manuscript, we explore this question and suggest ways to exploit the physical noise as a building block on which system level noise countermeasures can be further applied. The goal of this dissertation work is to quantify the intrinsic noise inherently present in a system and explore its manifestations through which it may be analyzed in a cryptographic context. This work could aid cryptographic designers in analyzing the intrinsic security of design implementations early in the development cycle, especially during design-stage evaluations. For research and academia, our work can be extended to explore different physical noise sources coupled to obtain a more holistic and consolidated view of the intrinsic security of design implementations. (FSA - Sciences de l'ingénieur) -- UCL, 2021

We (MPC) protocol based on garbled circuits which is both actively secure and supports the free-XOR technique, and which has communication complexity O(n) per party. This improves on a protocol of Ben-Efraim, Lindell and Omri which only achieved passive security, without support for free-XOR. Our construction is based on a new variant of LPN-based encryption, but has the drawback of requiring a rather expensive garbling phase. To address this issue we present a second protocol that assumes at least n/c of the parties are honest (for an arbitrary fixed value c). This second protocol allows for a significantly lighter preprocessing, at the cost of a small sacrifice in online efficiency. We demonstrate the practicality of our evaluation phase with an implementation.

The security and privacy research attempts to expose potential risks of adversaries and to prevent them. This thesis focuses on their evaluation. Our goal is to describe tools than can formally bound the risk that an adversary breaks the security or the privacy of a system. For this purpose, we leverage a methodology established in the field of side-channel analysis against embedded systems and apply it to other fields. Namely, we focus on security and privacy breaches that can occur when using localization, preference or brain-computer interface data in an open data setting. As previous works, we observe that most publicly available data reveals private information even if it is simplified or reduced before publication. Preventing attacks exploiting these information leakages is therefore challenging. Compared to previous work, we show that bounding the risks of a worstcase attacks is even more challenging. Tight bounds are only observed in overly simplified settings that strongly limit the interest of the data. In concrete (practically-relevant) settings, the bounds we observe are usually untight, revealing a possibility that stronger attacks could be mounted with more training data. Positively, we therefore provide tools that can bound the longterm security and privacy risks for some systems and simple statistical models, opening the question of generalizing such results for other systems and more complex (but faster converging) statistical models. (FSA - Sciences de l'ingénieur) -- UCL, 2021

Cryptography studies how to secure communications and information. The security of a cryptosystem depends on the secrecy of the underlying key. White-box cryptography explores methods to hide a cryptographic key into some software deployed in the real world.Classical cryptography only assumes that the adversary accesses the target cryptographic primitive in a black-box manner in which she can only observe or manipulate the input and output of the primitive, but cannot know or tamper with its internal details. The gray-box model further allows an adversary to exploit key- dependent sensitive information leaked from the execution of physical implementations. All sorts of side-channel attacks exploit some physical information leakage, such as the power consumption of the device. The white-box model considers the worst-case scenario in which the adversary has complete control over the software and its execution environment. The goal of white-box cryptography is to securely implement a cryptographic primitive against such a powerful adversary. Although the scientific community has proposed some candidate solutions to build white-box cryptography, all have proven ineffective. Consequently, this problem has remained open for almost two decades since the concept was introduced.The continuous growth in market demand and the emerging potential applications have driven the industry to deploy secretly-designed proprietary solutions. Al- though this paradigm of achieving security through obscurity contradicts the widely accepted Kerckhoffs' principle in cryptography, this is currently the only option for white-box cryptography. Security experts have reported how gray-box attacks could be used to extract keys from several publicly available white-box implementations. In a gray-box attack, the adversary adapts side-channel analysis techniques to the white-box context, i.e., to target computation traces made of noise-free run-time information instead of the noisy physical leakage. Gray-box attacks are generic since they do not require any a priori knowledge of the implementation and hence avoid costly reverse engineering. Some non-publicly scrutinized industrial white-box schemes in the market are believed to be under the threat of gray-box attacks.This thesis focuses on the analysis and improvement of gray-box attacks and the associated countermeasures for white-box cryptography. We first provide an in- depth analysis of why gray-box attacks are capable of breaking the classical white-box design which is based on table encodings. Next, we introduce a new gray-box attack named linear decoding analysis and show that linearly encoding sensitive information is insufficient to protect the cryptographic software. Afterward, we describe how to combine state-of-the-art countermeasures to resist gray-box attacks and comprehensively elaborate on the (in)effectiveness of these combined countermeasures in terms of computation complexity. Finally, we introduce a new attack technique that exploits the data-dependency of the targeted implementation to substantially lower the complexity of the existing gray-box attacks on white-box cryptography. In addition to the theoretical analyses and new attack techniques introduced in this thesis, we report some attack experiments against practical white-box implementations. In particular, we could break the winning implementations of two consecutive editions of the well-known WhibOx white-box cryptography competition., La cryptographie est la science de la protection des communications et des données. La sécurité d’un cryptosystème dépend du secret de la clé sous-jacente. La cryptographie en boîte blanche explore les méthodes permettant de cacher une clé dans un logiciel cryptographique déployé dans le monde réel.La cryptographie classique suppose que l’adversaire accède à la primitive cryptographique ciblée en boîte noire. Cela signifie qu’elle ne peut qu’observer et manipuler les entrées et les sorties de la primitive, mais ne peut pas connaître ou altérer son état interne. Le modèle en boîte grise permet en outre à un adversaire d’observer des informations sensibles qui sont divulguées lors de l’exécution d’une implémentation de la primitive. Toutes sortes d’attaques par canaux auxiliaires exploitent certaines fuites d’informations physiques, telles que la consommation électrique de l’appareil. Le modèle en boîte blanche considère le scénario le plus défavorable dans lequel l’adversaire a un contrôle total sur le logiciel cryptographique et sur son environnement d’exécution. Le rôle de la cryptographie en boîte blanche est d’implémenter une primitive cryptographique de façon à protéger la clé secrète contre un tel adversaire. Bien que la communauté scientifique ait tenté à plusieurs reprises de solutionner ce problème, ces tentatives se sont toutes révélées inadéquates. Par conséquent, la construction d’une solution de cryptographie en boîte blanche est resté un problème ouvert depuis l’introduction du concept il y a deux décennies.L’émergence d’applications avec de fortes contraintes de sécurité logicielle a poussé l’industrie à développer des solutions propriétaires dont la sécurité repose (en partie) sur des secrets de conception. Bien que ce paradigme de sécurité par l’obscurité contredise le principe de Kerckhoffs largement admis en cryptographie, c’est actuellement la seule option s’offrant à l’industrie pour répondre au besoin de cryptographie en boîte blanche. Des experts en sécurité ont récemment démontré comment certaines attaques en boîtes grise pouvaient être utilisées pour extraire les clés de plusieurs implémentations en boîte blanche accessibles publiquement. Dans une attaque en boîte grise, l’adversaire adapte des techniques d’analyse par canaux auxiliaires au contexte boîte blanche, en replaçant la fuite physique par des traces de calcul faites des valeurs intermédiaires non-bruitées observées lors de l’exécution. Les attaques en boîte grise sont génériques car elles ne nécessitent aucune connaissance a priori de l’implémentation et évitent ainsi la nécessité pour l’attaquant de recourir à une rétro-ingénierie coûteuse. Il semble que certaines solutions de cryptographie en boîte blanche actuellement déployée et n’ayant pas fait l’objet d’un examen public soient menacées par ce type d’attaques en boîte grise.Cette thèse se concentre sur l’analyse et l’amélioration des attaques en boîte grise et des contre-mesures associées pour la cryptographie en boîte blanche. Nous présentons tout d’abord une analyse approfondie des raisons pour lesquelles les attaques en boîte grise basiques sont capables de casser la technique classique de cryptographie en boîte blanche basée sur les encodages de tables. Nous proposons également de nouvelles techniques d’attaque en boîte grise significativement plus efficace contre ce type d’encodages. Nous introduisons ensuite une nouvelle attaque en boîte grise appelée analyse par décodage linéaire qui permet de déjouer toute méthode de protection basée sur un encodage linéaire des variables internes au calcul. Par la suite, nous étudions la combinaison de différentes contre-mesures pour résister aux attaques en boîte grise et analysons en détail la complexité d’attaques avancées contre ces contre-mesures combinées. Nous introduisons enfin une nouvelle technique d’attaque qui exploite le graphe de calcul de l’implémentation ciblée pour réduire considérablement la complexité des attaques en boîte grise sur la cryptographie en boîte blanche. Outre les analyses théoriques et nouvelles techniques d’attaque introduites dans cette thèse, nous rapportons plusieurs expériences d’attaque pratique contre divers implémentations en boîte blanche. Nous démontrons notamment comment nous avons pu casser les implémentations gagnantes des deux éditions consécutives de la compétition WhibOx., 密码学是一门研究保护数据和通信安全的科学。一个密码系统的安全 性取决于其密钥的保密性。白盒密码学探索在现实世界中部署的软件中隐 藏密钥的方法。经典密码学仅假定敌手以黑盒的方式访问被研究的密码学原语, 在这 种方式中，她只能观察或操作原语的输入和输出，而无法知道或篡改其内 部细节。灰盒模型进一步允许敌手利用物理实现执行过程中泄露的与密钥 相关的敏感信息。各种侧信道攻击都是利用一些物理信息泄露，比如设备 的功耗。白盒模型考虑的是最坏的情况，即敌手完全控制了软件及其执行 环境。白盒密码学的目标即是在敌手拥有上述强大能力的情况下，给出密 码学原语的安全软件实现。尽管学术界提出了一些构建白盒密码学的候选 方案，但事实证明这些方案都无效。因此，自概念提出以来，这个开放问 题持续存在了近二十年。白盒密码市场需求的持续增长和新兴的潜在应用促使工业界采用秘密 设计的专有解决方案。尽管这种通过模糊来实现安全性的范例与密码学中 被广泛接受的 Kerckhoffs 原则相悖，但这是在当前困境中的无奈之举。安 全专家报道了如何使用灰盒攻击从几种公开的白盒实现中提取密钥。在灰 盒攻击中，敌手将侧信道分析技术应用到白盒密码学中。她的研究对象是 从软件运行时收集不带任何噪音计算数据而非带有噪声的物理泄漏。灰盒 攻击是一种通用攻击，因为它们不需要关于攻击对象的任何先验知识，从 而避免了代价高昂的逆向工程。市场上一些未经公开审阅的工业白盒计划 被认为正受到灰盒攻击的威胁。本论文主要研究针对白盒密码学进行的灰盒攻击的分析与改进以及相 关对策。首先，我们深入分析了为什么灰盒攻击能够打破经典的基于编码 表的白盒设计。接下来，我们介绍了一种新的称为线性解码分析的灰盒攻 击，并阐释了仅通过对敏感信息进行线性编码的方式来保护软件中的密钥 是不足够的。随后，我们将描述如何通过组合最新的对策来抵抗灰盒攻击， 并从计算复杂性的角度全面阐述这些组合对策的有效性和无效性。最后， 我们介绍了一种新的攻击技术，该技术利用目标实现的数据依赖性来显著 降低现有灰盒攻击应用在白盒密码学的复杂性。本论文除了介绍的理论分 析和新的攻击技术外，还报告了一些针对实际白盒实现的攻击实验。特别 的是，我们连续两届打破了著名的 WhibOx 白盒密码学竞赛中的获胜实现。

One of the goals of modern cryptography is to prevent an adversary from making forgeries. That is, sending a message which the receiver believes valid while not sent by a genuine sender. For "black box" adversaries only able to access the inputs and outputs a cryptographic algorithm, many efficient solutions exist and provide strong mathematical security guarantees. Over the last decade, various research advances have shown that preventing black box attacks is not sufficient. For example, so-called side-channel adversaries can also access physical quantities produced during the cryptographic computations. Thanks to these physical leakages, very efficient forgery attacks can be performed, for example by extracting the long-term cryptographic keys.\ In this thesis, we propose a formal solution to the problem of authenticity in the presence of side-channel leakage. For this purpose, we introduce a new theoretical framework that allows capturing security against side-channel attacks, explain what security we aim for and how we model physical leakages, and then build constructions for which the physical security can be reduced to clear assumptions thanks to rigorous proofs. In particular, our proofs indicate which part of an implementation must be strongly protected against side-channel attacks and which part can leak (sometimes in full) with limited consequences. For example, we show that it is possible to reduce the security of full fledged authentication schemes to standard black box security properties and only requiring strong protections against side-channel attacks for one execution of its underlying cryptographic primitive. (FSA - Sciences de l'ingénieur) -- UCL, 2020

While rich medical, behavioral, and socio-demographic data are key to modern data-driven research, their collection and use raise legitimate privacy concerns. 91% of Americans and 80% of Europeans believe that they lost control over their data. De-identification, the process of anonymizing datasets before sharing them, has been the main paradigm used in research and elsewhere to share data while preserving people’s privacy. Yet numerous supposedly anonymous datasets have recently been released and re-identified by researchers and journalists. Are our data truly anonymous and our information safe? This thesis constitutes, firstly, a critical review of how data anonymization practices are currently evaluated, spanning from disclosed medical and demographics microdata to high-dimensional datasets, as well as methods to release aggregated statistics instead of raw data. This thesis builds, secondly, new models and frameworks to estimate the anonymity of data collections and suggests modern ways to release sensitive personal data while limiting privacy breaches. (FSA - Sciences de l'ingénieur) -- UCL, 2019

Since their discovery in the late 90's, side-channel attacks have been shown to be a great threat to the security of cryptographic implementations. In addition to the standard inputs and outputs of an algorithm, these attacks exploit the leakages coming from its implementation. As this additional information was not taken into account during the design of the standard schemes, they have been broken. A wide range of countermeasures has then been developed to increase the resilience of cryptographic schemes against these attacks. However, these countermeasures do not prevent attacks, but rather make them more complex to perform. As a result, the actual security of a given implementation needs to be tested in practice. A way to assess the security of an algorithm is to actually attack it in two steps. The first one, that we denote by information extraction, focuses on the way to use the information arising from the leakages as optimally as possible. The second one, that we denote by information exploitation, focuses on the way to use computational power to mitigate the lack of side-channel information after its extraction. This thesis follows this strategy and tackles both of these problems in two parts. In the first one, we focus on the leakage exploitation in the case of block ciphers. In this respect, we present new key enumeration and rank estimation algorithms and study their applicability. In the second part, we focus on the leakage extraction against elliptic curve cryptography. In that purpose, we present a method to use most of the available information against scalar multiplication algorithms through horizontal differential power attacks. (FSA - Sciences de l'ingénieur) -- UCL, 2018

Integrated circuits are now deployed in a continuously increasing range of applications. For many of them, sensitive data is manipulated, leading to technical and legal issues regarding its security. In this context, protection mechanisms are usually included in order to prevent various types of adversaries. At the most abstract level, cryptographic algorithms and protocols ensure that it is theoretically feasible to communicate privately and to guarantee message authenticity. More practically, various type of physical attacks can take advantage of features and imperfections in cryptographic implementations. Well-known threats are the cases of side-channel adversaries (taking advantage of unintended information leakages, e.g. due to the power consumption of the implementations) or fault adversaries (trying to force the implementation to perform erroneous computations). In this work, we are concerned with an even more powerful type of physical adversary, next denoted as the hardware Trojan adversary. In summary, the hardware Trojan adversary is not only able to observe the implementation at run time, but to maliciously modify its hardware at manufacturing time. Typical examples of hardware Trojans are “cheat codes” (e.g., sending the secret data under some rare input pattern) or “time bombs” (e.g., sending secret data at some time). Such extreme adversaries are motivated by the increasing need of trust in integrated circuits. That is, recent news have shown that untrusted software is deployed and exploited (as typically emphasized by the Snowden revelations). Ultimately, this implies that the design of secure systems has to start by trusted hardware -- a problem for which little solutions exist so far. More precisely, the state-of-the-art literature suggests that detecting hardware Trojans is both technically challenging (if not impossible), and hard to formalize (which implies hard to quantify risks). Hence, an alternative is to prevent hardware Trojans actively. In this respect, a recent work published at ACM CCS 2016 introduced a theoretically founded way to mitigate hardware Trojans thanks to “testing amplification”. It essentially exploits secret sharing and multiparty computation to prevent cheat codes, and redundant randomized testing to prevent time bombs. Based on this solution, it is possible to render the probability of a hardware Trojan attack exponentially small, if the run time of the circuit is limited. In this paper, we extend this theoretical work towards practice in two important directions. First, we designed a hardware architecture for a Trojan-resilient circuit for two block ciphers (the standard AES and lightweight Mysterion), based on an improved multi-party computation protocol, and implemented the architecture on a concrete prototype connecting three FPGAs. This allowed us to evaluate the performances of such a Trojan-resilient circuit on a concrete basis, confirm practical applicability, and to identify bottlenecks and tracks for improvement. Second, one core assumption of such Trojan-resilient circuits is the existence of a small “trusted master circuit”, of which the size has to be minimized. We analyzed the implementation of such a master, confirmed that it is indeed minimum compared to the implementation of the full block ciphers, confirming theoretical analyses with quantitative experimental data. We additionally investigated the effectiveness of a side-channel based hardware Trojan detection for such a small master and show positive results for the practically-relevant case of time bombs. Master [120] : ingénieur civil électricien, Université catholique de Louvain, 2017

Les smartphones sont presque omniprésents au quotidien et les possibilités qu'ils offrent sont de plus en plus variées. L'importance des données accessibles pose question quant à la manière dont elles sont sécurisées. Fréquemment, un simple code de sécurité permet de déverrouiller un téléphone et d'atteindre l'essentiel de ces données. Un utilisateur aura tendance à cacher son écran lorsqu'il tape son code, sans se rendre compte qu'il est exposé malgré cette précaution. L'objectif de ce travail est de proposer une méthode de reconnaissance de codes de sécurité à partir d'images volées. Les images volées sont capturées par le smartphone de l'attaquant. L'algorithme permet d'identifier le code saisi grâce aux reflets de l'écran dans les verres de lunettes de soleil. La méthode est essentiellement basée sur des outils de traitement d'images. Ce travail commence par une présentation des principales méthodes récentes d'identification de données à partir d'images volées. Ensuite, il continue en abordant les notions théoriques et les outils de traitement d'images utilisés. Par après, la méthode ainsi que les algorithmes implémentés sont détaillés. Pour finir, nous présentons les résultats obtenus dans le cas d'images isolées et de vidéos, à partir d'ensembles de données spécialement acquises pour ce travail. Master [120] : ingénieur civil électricien, Université catholique de Louvain, 2017

Embedded security is a field studying how the physical implementations of cryptosystems can weaken the integrity of their hidden secrets. Power analysis attacks are one of the most spread side-channel attacks and take advantage of a device’s power consumption to retrieve sensitive information about it. One typical countermeasure to thwart those attacks is masking, which consists in splitting the sensitive data into multiple independent shares. The objective of this master thesis is to propose a physical security analysis of different AES implementations on an 8-bit Atmel micro-controller. This work starts by describing the ChipWhisperer-Lite, the platform that was used to record all the power traces. It continues by studying an unprotected version of the AES, and shows that its execution leaks information that can be easily exploited to recover the key with some basic attacks. It then presents the implementation of several state-of-the-art software masking schemes and compares them in terms of execution time and required randomness. Finally, it analyses their practical security level, based on two different leakage detection tests and univariate attacks. Master [120] : ingénieur civil électricien, Université catholique de Louvain, 2017

Avec le nombre grandissant de bases de données contenant maintes informations sur maints individus, les questions de la vie privée et de l'anonymat reviennent souvent aujourd'hui. Les firmes doivent d'ailleurs de plus en plus répondre à des critères visant à garder une certaine sécurité, un certain anonymat dans leurs bases de données. Il semble donc nécessaire d'avoir une estimation de l'information disponible au travers de ces données, notamment au travers de celles concernant la localisation. Pour ce faire nous utiliserons les métriques de l'information perçue et du taux de succès nous permettant de quantifier le niveau de location privacy via la caractérisation des utilisateurs. Nous tenterons de répondre à la question de savoir combien de données sur les utilisateurs sont nécessaires pour pouvoir en faire une bonne caractérisation et à quel point cette caractérisation permet d'identifier l'utilisateur qui a généré les données. Ces quantificateurs se servant de probabilités à posteriori, nous pourrons comparer plusieurs outils permettant d'en obtenir, à savoir le modèle par noyau, le modèle discret et celui par maximisation d'espérance ainsi que des méthodes permettant d'obtenir directement des pseudo-probabilités, telles que la méthode des K plus proches voisins et celle des arbres des décision. Différentes techniques de défense telles que l'agrégation de l'espace et le bruitage de données seront également testées afin d'essayer d'augmenter la location privacy. Les données utilisées seront premièrement des données simulées d'utilisateurs se trouvant dans l'espace à $2$ dimensions et deuxièmement des données réelles d'utilisateurs présents sur la côte Est des Etats-Unis. Les résultats montrent que tous les outils d'analyse que nous considérons comme méthode d'attaque donnent une information perçue élevée dans les données simulées et surtout que le taux de succès atteint est très souvent maximal. Les données réelles n'offriront pas plus de location privacy et les résultats obtenus sur celles-ci semblent rester aussi convaincants que ceux des données simulées. Les moyens de défense permettent toutefois d'augmenter ce niveau de location privacy mais pas de façon miraculeuse à moins bien sûr d'altérer énormément les données. Au vu de ces résultats il semble évident que la réponse à notre question est malheureusement celle redoutée: oui, les données permettent bien trop facilement à un attaquant quelconque d'obtenir des informations privées quant aux individus se retrouvant dans une base de données de géolocalisation. Master [120] : ingénieur civil en mathématiques appliquées, Université catholique de Louvain, 2017

This thesis focusses on privacy considerations for access authentication systems. Today, access authentication systems are used in every situations and nearly everywhere. Those authentication systems create metadata 1 , such as access logs and punctual identifications. By aggregating those metadata which have no value alone, we can guess habits and comportments of users. Current authentication systems can leak those metadata and so compromise privacy. Solutions have to be implemented in order to reduce the amount of those leaks and their relevancy. This thesis covers different systems that can reduce those attacks on privacy. First chapter of this Thesis exposes current systems and practices in access tokens and access authentication systems. It explains how access tokens work, especially for Radio Frequency IDentification (RFID) tokens. Those are also categorized and compared technically. This chapter also covers some implementation standards for access authentication systems. This thesis also introduces some security risks related to current systems. Second chapter focusses on a particular system that uses MIFARE DESFire EV1 tokens for access authentication. The privacy aspect and protection systems implemented in this token are evoked and discussed. This particular authentication system implements some protections for privacy but those solutions can still be improved. Those weaknesses are discussed and in term of security but also for the privacy of the user. Those systems are often used for cases where privacy is critical although those are not adapted. A possible improvement, which is the switch to transparent mode for the communication with the readers, is exposed in Third chapter of this document. Transparent mode applied to the MIFARE DESFire EV1 authentication system is an improvement for security and privacy. This chapter covers the improvements but also an implementation of such protocol on an existing authentication system. However, such systems cannot be used in every situations. For example, some companies use those systems for public transportation whereas the user’s privacy is not perfect. Such cases have to use more adapted systems. Group signature is a scheme that can help to improve privacy. This topic is covered in Fourth chapter of this thesis where theoretical information are given. This chapter presents cryptographic schemes that can be used for group signature and authentication. Those schemes are compared theoretically and discussed against practical considerations. Finally, last chapter presents an implementation of group signature scheme for smartphones. This system is confronted to the use case of a music concerts subscription and is benchmarked for this use case. A proof of concept is also developed and presented in this chapter. It uses Android smartphones as Prover and is aimed to prove the usability and the feasibility of such system with today’s technologies. Master [120] : ingénieur civil électricien, Université catholique de Louvain, 2016

Secure multi-party computation is a problem where a number of parties want to compute a function of their inputs in a secure way. Security implies correctness of the outputs and privacy of the inputs, even when some parties are cheating. This problem has been at the centre of cryptography research for almost 30 years. However, it is only recently that practical applications have been developed, for example, in auctions, voting systems or data mining. In this vein, this thesis aims to securely solve classical algorithmic problems using multi-party computation techniques, but departs from the traditional focus on problems that admit a simple circuit representation to investigate problems with a richer structure. First, this work presents new sorting algorithms based on a unary representation of integers. These algorithms can be used efficiently as subroutines for applications that make use of the unary representation, for example, in addressing mechanisms. Second, a new procedure to obtain a fair division of a heterogeneous resource between competing parties is provided. This procedure does not have a counterpart in game theory and the equilibrium reached dominates the ones that were previously known in unmediated procedures. Finally, the first secure single-source shortest path and maximum flow algorithms are developed. Depending on the settings, these algorithms raise intriguing questions in terms of asymptotic complexity compared to their traditional counterparts. (FSA - Sciences de l'ingénieur) -- UCL, 2015

This thesis sets as goal the study and development of cryptographic multi-party protocols offering the properties of verifiability and privacy. The verifiability property guarantees the protocols participants and/or observers that the result of the execution of the protocol is exactly what is expected from a honest execution of the protocol. On the other hand, the privacy property ensures the participants that their private information is not leaked by executing the protocol. The thesis targets real-world applications as well as any multi-party function. The first part of the work focus on cryptographic voting systems. In this case, the function to evaluate is rather simple -- e.g. a sum of yes/no votes -- and, we show how we conciliate the verifiability with the privacy to obtain a cryptographic voting system that offers a perfectly private audit trail of its execution. A perfectly private audit trail means that it contains no information about the voters' votes whatsoever. In addition, the trail computationally guarantees the observers that the tally of the votes is correct. Next, we extend our study to encompass more complex functions. We work on combinatorial problems such as graph problems. In this part, following the traditional approach of secure multi-party computation, we investigate potential sources of privacy leakages that appear when turning the unsecured version of an algorithm into its secure version. We propose solutions to prevent these privacy leakages through algorithms for securely sorting shared lists and securely computing the shortest path and the maximum flow in shared graphs. In the last part of the thesis, we follow a different approach than the traditional secure multi-party computation one. In our approach, we rely on a third party (worker) that is entrusted with the privacy of the protocol participants' inputs. We show that several important gains can be made in this setting. We propose a generic protocol that can be used to evaluate any multi-party function while offering a perfectly private audit trail of its computation. This protocol is mainly non-interactive and offers the worker the possibility to use his own algorithms. Finally, the solutions obtained in this thesis have been implemented. The secure multi-party protocols are available in an online prototype that can be used as such or to develop any desired new multi-party application that offers perfect privacy and computational verifiability. (FSA - Sciences de l'ingénieur) -- UCL, 2015

In this PhD dissertation, we investigate how to solve some classical combinatorial optimization problems in network flows and their applications, using secure multiparty computation. Our study highlights the differences between traditional and secure adaptations of some algorithms to later test its implementation. It also explores various trade-offs between performance and security. We provide protocols that can be used as building blocks to solve more complex problems. Additionally, we report on practical applications, more specifically, we study the problem of securely building auction mechanisms with transmission constraints. We focus on improving performance for real life applications. We report on the design of a specific Object Oriented implementation of the necessary secure multiparty computation protocols used for the experimentation on practical applications. Areas of interest for our work can be found in: auction markets, communication networks, routing data from rival company hubs, distribution problems, amongst others. (FSA - Sciences de l'ingénieur) -- UCL, 2015

Since the late 90's side-channel attacks have been a threat for cryptographic implementations. They use observations of physical features of a device while it computes cryptographic algorithms. These leakages can give information about the key. A common countermeasure against such attacks is masking. The main idea of masking is to randomize the internal state. In consequence an adversary must combine of several leakages to mount the attack. Masking schemes have an impact on the efficiency of the implementations. In this thesis, we explore different solutions to improve the efficiency of masking implementations. Firstly, we explore solutions for masking implementations for the AES. We investigate the use of amortization technique to reduce the cost of polynomial masking. We also propose a new way to combine Boolean secure multiplications to reduce the cost of masking. Next, we focus on the assumptions used for proofs of masking. We show that the use of low entropy masking schemes can be risky. We also show how to convert proofs in the probing model into proofs in the transition based model. Then, we propose several easier-to-build strategies for masking block ciphers. We present three block ciphers. Finally, we focus on leakage resilience and compare the security that can be obtained by using either leakage-resilient construction, masking or their combination. (FSA - Sciences de l'ingénieur) -- UCL, 2015

Since the late 90s, the implementation of cryptosystems on smart card faces two kinds of attacks : side-channel attacks and fault injection attacks. Countermeasures are then developed and validated by considering a well-defined attacker model. This thesis focuses on the protection of symmetric cryptosystems against side-channel attacks. Specifically, we are interested in masking countermeasures in order to tackle high-order attacks for which an attacker is capable of targeting t intermediate values. After recalling the analogy between masking countermeasures and secret sharing schemes, the construction of secret sharing schemes from linear codes introduced by James L. Massey in 1993 is presented.By adapting this construction together with tools from the field of Multi-Party Computation, we propose a generic masking countermeasure resistant to high-order attacks. Furthermore, depending on the cryptosystem to protect, this solution optimizes the cost of the countermeasure by selecting the most appropriate code. In this context, we propose two countermeasures to implement the AES cryptosystem. The first is based on a family of evaluation codes similar to the Reed Solomon code used in the secret sharing scheme of Shamir. The second considers the family of self-dual and self-orthogonal codes generated by a matrix defined over GF(2) or GF(4). These two alternatives are more effective than masking countermeasures from 2011 based on Shamir's secret sharing scheme. Moreover, for t=1, the second solution is competitive with usual solutions.; Depuis la fin des années 90, les cryptosystèmes implantés sur carte à puce doivent faire face à deux grandes catégories d'attaques : les attaques par canaux cachés et les attaques par injection de fautes. Pour s'en prémunir, des contre-mesures sont élaborées, puis validées en considérant un modèle d'attaquant bien défini. Les travaux réalisés dans cette thèse se concentrent sur la protection des cryptosystèmes symétriques contre les attaques par canaux cachés. Plus précisément, on s'intéresse aux contre-mesures de masquage permettant de se prémunir des attaques statistiques d'ordre supérieur pour lesquelles un attaquant est capable de cibler t valeurs intermédiaires. Après avoir rappelé l'analogie entre les contre-mesures de masquage et les schémas de partage de secret, on présente la construction des schémas de partage de secret à partir de codes linéaires, introduite par James L. Massey en 1993. En adaptant cette construction et des outils issus du calcul multi-parties, on propose une méthode générique de contre-mesure de masquage résistante aux attaques statistiques d'ordre supérieur. De plus, en fonction des cryptosystèmes à protéger et donc des opérations à effectuer, cette solution permet d'optimiserle coût induit par les contre-mesures en sélectionnant les codes les plus adéquats. Dans cette optique, on propose deux contre-mesures de masquage pour implanter le cryptosystème AES. La première est basée sur une famille de code d'évaluation proche de celle utilisée pour le schéma de partage de secret de Shamir, tandis que la seconde considéré la famille des codes auto-duaux et faiblement auto-duaux ayant leur matrice génératrice à coefficient sur F2 ou F4. Ces deux alternatives se révèlent plus efficaces que les contremesures de masquage publiées en 2011 et basées sur le schéma de partage de secret de Shamir. De plus la seconde s'avère compétitive pour t=1 comparée aux solutions usuelles.

The Internet-of-Things (IoT) is an emerging paradigm that aims to integrate technology into the human environment, rather than the reverse. By connecting together a multitude of sensors and devices, through cross-correlation and increased contextual awareness, interactions with such connected devices is set to become more relevant and less intrusive. At the heart of this IoT are the individual Wireless Sensor Nodes (WSNs), which are limited in their autonomy by the energy they can store or harvest. This thesis therefore aims to decrease the energy consumption of these nodes in an effort to increase their lifespans. Three main techniques were developed in this thesis to achieve that goal. Firstly, a processor was developed to provide high performance for a low average energy consumption (7.7µW/MHz at 50MHz). This enables on-node processing, thereby reducing the usage of the power-hungry wireless link. Secondly, a circuit design technique was developed to increase the average speed of combinatorial circuit blocks beyond that traditionally achievable, by adjusting the processing time to the data actually encountered, rather than the theoretical worst-case. By increasing the processing speed, the node can complete operations faster, thus allowing longer sleep times and lower overall energy consumption. Lastly, in view of the wide range of potential processing requirements inherent in WSN applications, a dual-processor technique was developed to better match each situation. Transparent from a user’s perspective, the resulting system can meet high-performance targets while at the same time process low-priority tasks during 'idle' periods. Together, the techniques proposed in this thesis can enable lower-power systems, and is a step towards a new generation of exciting applications. (FSA - Sciences de l) -- UCL, 2014

With the emergence of the internet of things, the research surrounding the design of cryptographic algorithms suited for constrained environments has rapidly gained ground. This fast development of new security primitives and their implementation on electronic devices has led to several concerns in terms of fair evaluation, physical security and protection of their intellectual property (IP). These can be summarized with the following questions: 1. How can we fairly compare the performances of algorithms? How do lightweight algorithms compare to the standard ones? What is the impact of design choices on the implementation results? 2. To what extent do countermeasures against side-channel attacks (SCA) improve security and at which cost? What is the impact of new technologies on the physical security and efficiency of cryptographic implementations? 3. How to protect IPs in a way that is both flexible and secure? To answer these questions, we first propose different evaluation frameworks which allow us to compare the efficiency of cryptographic algorithms. From the obtained results, we extract some general design guidelines and show that normalized metrics (such as energy) are generally more illustrative. We then come up with more efficient implementations of the shuffling countermeasure which is an important solution to improve security against SCA. We also present the first implementation of the randomized look up table countermeasure. Finally, we propose a new flexible IP protection infrastructure exploiting the implementation power consumption as a signature. (FSA - Sciences de l) -- UCL, 2014

Technology is linking the slightest of our actions to the virtual world. In such connected environments, cryptography aims at building schemes with provable security in order to mathematically protect the users' security in electronic exchanges. Relying on the existence of pairings in bilinear groups wherein the discrete logarithm problem is hard, this thesis puts forth mechanisms to efficiently enhance the privacy in three of the most fundamental cryptographic primitives, namely, digital signatures, encryption schemes and zero-knowledge proofs. Furthermore, these mechanisms support public verifiability so as to force the honesty of all participants in the standard model. We first focus on group signatures, a primitive proposed some 20 years ago, for which we propose the first efficient revocation mechanisms, overcoming the main obstacle to the deployment of this primitive in practical applications. We then focus on P-homomorphic signatures that make it possible to modify a signed message in a controlled way. In particular, we propose new mechanisms providing structure-preserving linearly homomorphic signatures, from which we build the first constant-size non-malleable commitments compatible with standard proof systems, as well as a generalization of this construction into a generic transformation. Finally we further investigate the unexpected applications of this kind of malleable signatures to non-malleable cryptography. This leads us to new proof systems for linear languages which in turn provide the most efficient publicly verifiable CCA-secure threshold encryption to date, and other new extensions. (FSA - Sciences de l) -- UCL, 2014

With technology scaling, electronic devices are becoming ubiquitous in everyday applications (smartcards, car keys,...). Many of these applications require security or privacy features for which cryptography is an essential building block. In the context of small embedded devices like smartcards, the security of cryptographic primitives is usually assessed using different types of cryptanalyses. For example, classical cryptanalysis targets the algorithm as a mathematical object. However, these devices are often physically accessible to the adversary, additionally allowing him to target the implementations of cryptographic algorithms, with physical cryptanalyses. In this setting, side-channel attacks exploiting (for example) the power consumption of microelectronic circuits have received increasing attention since their introduction 15 years ago, as they raise important challenges for secure hardware manufacturers Evaluating the side-channel security of an implementation is a non-trivial task: there are no hard-and-fast rules to decide what is the optimal way to extract information from a side-channel leakage, or how to efficiently exploit it to break a cryptosystem. This thesis tackles this problem and aims at developing and analyzing new tools and metrics in order to better answer both questions. In the extraction part, we present a refined metric for evaluating the quantity of information available in actual side-channel measurements. We illustrate its importance by adapting it to the evaluation of various countermeasures introduced in the literature. In the exploitation part, we develop a new attack called Algebraic Side-Channel Attack that exploits at the same time all the information available in the leakages and the adversary's computational power. It can succeed in very challenging scenarios using as few as one single leakage trace. We also present a new enumeration algorithm that can be integrated into any DPA attack in order to increase its success rate at the cost of more intense computations. We finally combine these observations by arguing about the need of new and properly defined classes of physical adversaries. (FSA 3) -- UCL, 2012

This thesis deals with side channel attacks against hardware implementations of cryp- tographic algorithms. Studies conducted in this document are therefore in place where an adversary has access to noisy observations of intermediate results of a cryptographic computation. In this context, many attacks are dedicated with their countermeasures, but their relevance and their implementation are still unclear. This thesis initially focuses on the relevance of existing attacks and potential links between them. A formal classification is proposed as well as selection criteria. Based on this study, a generic efficient attack is described and analysed in depth. In a second step, the implementation of common countermeasures is studied, leading to the creation of an application scheme mixing them to achieve a better efficiency / security trade off. Cette thèse s’intéresse aux attaques par canaux auxiliaires contre les implantations matérielles d’algorithmes cryptographiques. Les études conduites dans ce document se placent donc dans le cadre où un adversaire a accès à des observations bruitées des résultats intermédiaires d’un calcul cryptographique. Dans ce contexte, de nombreuses attaques existent avec leurs contremesures dédiées, mais leur pertinence et leur mise en pratique restent encore floues. Cette thèse s’intéresse dans un premier temps à la pertinence des attaques existantes et aux possibles liens qui les unissent. Une classification formelle est proposée ainsi que des critères de choix. Sur la base de cette étude, une attaque générique perfor- mante est décrite et analysée en profondeur. Dans un second temps, la mise en pratique des contremesures actuelles est étudiée, donnant lieu à la création d’un schéma d’application les mélangeant pour atteindre de meilleurs compromis efficacité/sécurité. (FSA 3) -- UCL, 2012

Highly power-constrained secure applications such as RFIDs, present a great challenge for circuit designers who try to determine the best tradeoff between security and performance. “Computationally” secure applications are not secure anymore due to the physical information leakage of the hardware implementations that use static CMOS (e.g. the power consumption, ... etc.). These types of physical information leakage are exploited by side-channel attacks. Consequently, it is the responsibility of circuit designers to develop new techniques that maximize the security of the implementation with minimum cost in terms of power consumption and area in light of the growing concern of variability associated to nano-CMOS technologies as well. Hardware-level solutions, specially DDL styles are seemingly attractive. Unfortunately, most of the proposed DDL styles in the literature consume and occupy a minimum of 2x the power and area of static CMOS, respectively. The work of this PhD thesis aims at optimizing the design of the previously introduced DDSLL style for low power, small area and adequate security enhancement compared to static CMOS. A DDSLL S-box is implemented on a LP 65 nm CMOS technology and it consumes ~ power to static CMOS and occupies ~ area. Also, DDSLL is 10x harder to attack than static CMOS. Even though the security gain of DDSLL is not sufficient compared to other types of countermeasures, its low power consumption and area overheads give more room to combine countermeasures. (FSA 3) -- UCL, 2012

Modern cryptography responds to the need for security that has arisen with the emergence of communication appliances. However, its adapted integration in the wide variety of existing communication systems has opened new design challenges. Amongst them, this thesis addresses two in particular, related to hardware integration of cryptographic algorithms: constrained environments and side-channel security. In the context of constrained environments, we propose to study the interest of the Scalable Encryption Algorithm SEA for constrained hardware applications. We investigate both the FPGA and ASIC contexts and illustrate, using practical implementation results, the interest of this algorithm. Indeed, we demonstrate how hardware implementations can keep its high scalability properties while achieving interesting implementation figures in comparison to conventional algorithms such as the AES. Next, we deal with three complementary aspects related to side-channel resistance. We first propose a new class of dynamic and differential logic families achieving low-power performance with matched leakage of information to state of-the-art countermeasures. We then discuss a power consumption model for these logic styles and apply it to DyCML implementations. It is based on the use of the isomorphism existing between the gate structures of the implemented functions and the binary decision diagrams describing them. Using this model, we are not only able to predict the power consumption, and therefore attack such implementations, but also to efficiently choose the gate structures achieving the best resistance against this model. We finally study a methodology for the security evaluation of cryptographic applications all along their design and test phases. We illustrate the interest of such a methodology at different design steps and with different circuit complexity, using either simulations or power consumption measurements. (FSA 3) -- UCL, 2008