Search

Evaluation of side-channel leakage for cryptographic systems requires sound leakage detection procedures. The commonly used standard approach is the test vector leakage assessment (TVLA) procedure. We first relate TVLA to the statistical minimum p-value (mini-p) procedure, and propose a sound method of deciding leakage existence in the statistical hypothesis setting. An advanced statistical procedure, Higher Criticism (HC), is adopted to improve leakage detection when there are multiple leakage points. The HC-based procedure is optimal in side-channel leakage detection, because for a given number of traces with a given length, it detects the existence of leakage at the signal level as low as possibly detectable by any statistical procedure. Numerical studies show that our HC-based procedure perform as well as the mini-p based procedure when leakage signals are very sparse, and can improve the leakage detection significantly when there are multiple leakages.

Most leakage-resilient cryptographic constructions aim at limiting the information adversaries can obtain about secret keys. In the case of asymmetric algorithms, this is usually obtained by secret sharing (aka masking) the key, which is made easy by their algebraic properties. In the case of symmetric algorithms, it is rather key evolution that is exploited. While more efficient, the scope of this second solution is limited to stateful primitives that easily allow for key evolution such as stream ciphers. Unfortunately, it seems generally hard to avoid the need of (at least one) execution of a stateless primitive, both for encryption and authentication protocols. As a result, fresh re-keying has emerged as an alternative solution, in which a block cipher that is hard to protect against side-channel attacks is re-keyed with a stateless function that is easy to mask. While previous proposals in this direction were all based on heuristic arguments, we propose two new constructions that, for the first time, allow a more formal treatment of fresh re-keying. More precisely, we reduce the security of our re-keying schemes to two building blocks that can be of independent interest. The first one is an assumption of Learning Parity with Leakage, which leverages the noise that is available in side-channel measurements. The second one is based on the Learning With Rounding assumption, which can be seen as an alternative solution for low-noise implementations. Both constructions are efficient and easy to mask, since they are key homomorphic or almost key homomorphic.

Side-channel attacks generally rely on the availability of good leakage models to extract sensitive information from cryptographic implementations. The recently introduced leakage certification tests aim to guarantee that this condition is fulfilled based on sound statistical arguments. They are important ingredients in the evaluation of leaking devices since they allow a good separation between engineering challenges (how to produce clean measurements) and cryptographic ones (how to exploit these measurements). In this paper, we propose an alternative leakage certification test that is significantly simpler to implement than the previous proposal from Eurocrypt 2014. This gain admittedly comes at the cost of a couple of heuristic (yet reasonable) assumptions on the leakage distribution. To confirm its relevance, we first show that it allows confirming previous results of leakage certification. We then put forward that it leads to additional and useful intuitions regarding the information losses caused by incorrect assumptions in leakage modeling.

The use of Soft Physical Hash (SPH) functions has been recently introduced as a flexible and efficient way to detect Intellectual Property (IP) cores in microelectronic systems. Previous works have mainly investigated software IP to validate this approach. In this paper, we extend it towards the practically important case of FPGA designs. Based on experiments, we put forward that SPH functions-based detection is a promising and low-cost solution for preventing anti-counterfeiting, as it does not require any a-priori modification of the design flow. In particular, we illustrate its performances with stand-alone FPGA designs, re-synthetized FPGA designs, and in the context of parasitic IPs running in parallel.

In this paper, we evaluate the performances of state-of-the-art higher order masking schemes for the AES. Doing so, we pay a particular attention to the comparison between specialized solutions introduced exclusively as countermeasures against side-channel analysis, and a recent proposal by Roche and Prouff exploiting multiparty computation (MPC) techniques. We show that the additional security features this latter scheme provides (e.g., its glitch-freeness) come at the cost of large performance overheads. We then study how exploiting standard optimization techniques from the MPC literature can be used to reduce this gap. In particular, we show that “packed secret sharing” based on a modified multiplication algorithm can speed up MPC-based masking when the order of the masking scheme increases. Eventually, we discuss the randomness requirements of masked implementations. For this purpose, we first show with information theoretic arguments that the security guarantees of masking are only preserved if this randomness is uniform, and analyze the consequences of a deviation from this requirement. We then conclude the paper by including the cost of randomness generation in our performance evaluations. These results should help actual designers to choose a masking scheme based on security and performance constraints.

Generic side-channel distinguishers aim at revealing the correct key embedded in cryptographic modules even when few assumptions can be made about their physical leakages. In this context, Kolmogorov-Smirnov Analysis (KSA) and Partial Kolmogorov-Smirnov analysis (PKS) were proposed respectively. Although both KSA and PKS are based on Kolmogorov-Smirnov (KS) test, they really differ a lot from each other in terms of construction strategies. Inspired by this, we construct nine new variants by combining their strategies in a systematic way. Furthermore, we explore the effectiveness and efficiency of all these twelve KS test based distinguishers under various simulated scenarios in a univariate setting within a unified comparison framework, and also investigate how these distinguishers behave in practical scenarios. For these purposes, we perform a series of attacks against both simulated traces and real traces. Success Rate (SR) is used to measure the efficiency of key recovery attacks in our evaluation. Our experimental results not only show how to choose the most suitable KS test based distinguisher in a particular scenario, but also clarify the practical meaning of all these KS test based distinguishers in practice.

The pervasive diffusion of electronic devices in security and privacy sensitive applications has boosted research in cryptography. In this context, the study of lightweight algorithms has been a very active direction over the last years. In general, symmetric cryptographic primitives are good candidates for low-cost implementations. For example, several previous works have investigated the performance of block ciphers on various platforms. Motivated by the recent SHA3 competition, this paper extends these studies to another family of cryptographic primitives, namely hash functions. We implemented different algorithms on an ATMEL AVR ATtiny45 8-bit microcontroller, and provide their performance evaluation. All the implementations were carried out with the goal of minimizing the code size and memory utilization, and are evaluated using a common interface. As part of our contribution, we make all the corresponding source codes available on a web page, under an open-source license. We hope that this paper provides a good basis for researchers and embedded system designers who need to include more and more functionalities in next generation smart devices. © 2013 Springer-Verlag. ispartof: pages:158-172 ispartof: Lecture Notes in Computer Science vol:7771 pages:158-172 ispartof: CARDIS 2012 date:28 Nov - 30 Nov 2012 status: published

Variability is a central issue in deep submicron technologies, in which it becomes increasingly difficult to produce two chips with the same behavior. While the impact of variability is well understood from the microelectronic point of view, very few works investigated its significance for cryptographic implementations. This is an important concern as 65-nanometer and smaller technologies are soon going to equip an increasing number of security-enabled devices. Based on measurements performed on 20 prototype chips of an AES S-box, this paper provides the first comprehensive treatment of variability issues for side-channel attacks. We show that technology scaling implies important changes in terms of physical security. First, common leakage models (e.g. based on the Hamming weight of the manipulated data) are no longer valid as the size of transistors shrinks, even for standard CMOS circuits. This impacts both the evaluation of hardware countermeasures and formal works assuming that independent computations lead to independent leakage. Second, we discuss the consequences of variability for profiled side-channel attacks. We study the extend to which a leakage model that is carefully profiled for one device can lead to successful attacks against another device. We also define the perceived information to quantify this context, which generalizes the notion of mutual information with possibly degraded leakage models. Our results exhibit that existing side-channel attacks are not perfectly suited to this new context. They constitute an important step in better understanding the challenges raised by future technologies for the theory and practice of leakage resilient cryptography.

Side-channel cryptanalysis is a new research area in applied cryptography that has gained more and more interest since the midnineties. It considers adversaries trying to take advantage of the physical specificities of actual cryptographic devices. These implementationspecific attacks frequently turn out to be much more efficient than the best known cryptanalytic attacks against the underlying primitive seen as an idealized object. This paper aims to introduce such attacks with illustrative examples and to put forward a number of practical concerns related to their implementation and countermeasures.

Hardware implementations of the Advanced Encryption Standard (AES) Rijndael algorithm have recently been the object of an intensive evaluation. Several papers describe efficient architectures for ASICs (ASIC: Application Specific Integrated Circuit) and FPGAs (FPGA: Field Programmable Gate Array). In this context, the highest effort was devoted to high throughput (up to 20 Gbps) encryptiononly designs, fewer works studied low area encryptiononly architectures and only a few papers have investigated low area encryption/decryption structures. However, in practice, only a few applications need throughput up to 20 Gbps while flexible and low cost encryption/decryption solutions are needed to protect sensible data, especially for embedded hardware applications. This paper proposes an efficient solution to combine Rijndael encryption and decryption in one FPGA design, with a strong focus on low area constraints. The proposed design fits into the smallest Xilinx FPGAs (Xilinx Spartan-3 XC3S50), deals with data streams of 208 Mbps, uses 163 slices and 3 RAM blocks and improves by 68% the best-known similar designs in terms of ratio Throughput=Area. We also propose implementations in other FPGA Families (Xilinx Virtex-II) and comparisons with similar DES, triple-DES and AES implementations.

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

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

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

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