Broadcast Encryption and Traitor Tracing for Conditional Access Systems

In the context of the thesis we are studying the notions of broadcast encryption and traitor tracing in an industrial framework of conditional access systems related to Pay-TV. Broadcast encryption represents a cryptographic primitive which allows confidential transmission of content on a broadcast channel in such a way that only an authorized subset of users defined by the broadcaster are able to access it. Traitor tracing is a mechanism for identifying rogue sources who shared their decryption keys. Combined together, these two methods can be used to identify compromised terminals and instantaneously revoke them. Intuitively these two techniques are of high interest for Pay-TV systems with respect to the threats of today. Today, the majority of industrial security system are based on the tamper-resistance against attacks, such as those exploiting, for instance, different side channel information such as time, power consumption, electromagnetic emanations to name a few. However during recent years these attacks became more and more sophisticated. Therefore the aim of this thesis is to propose new schemes and mechanisms to improve the state-of-the-art for the conditional access systems and more specifically Pay-TV systems so that they rely even more on a solid cryptographic basis. As a matter of fact, even though many cryptographic schemes closely related to the subject of this thesis existed since many years in academia, none of them could have been deployed directly and efficiently in the context of large scale Pay-TV system which puts a number of heavy constraints on the bandwidth as well as on the computational complexity of the receivers. Consequently we will also describe the system and its constraints in order to simplify the task of development and integration of future schemes in these two academic domains in the context of practical environment.

Bringing Theory Closer to Practice in Post-quantum and Leakage-resilient Cryptography

Alexandre Raphaël Duc

Modern cryptography pushed forward the need of having provable security. Whereas ancient cryptography was only relying on heuristic assumptions and the secrecy of the designs, nowadays researchers try to make the security of schemes to rely on mathematical problems which are believed hard to solve. When doing these proofs, the capabilities of potential adversaries are modeled formally. For instance, the black-box model assumes that an adversary does not learn anything from the inner-state of a construction. While this assumption makes sense in some practical scenarios, it was shown that one can sometimes learn some information by other means, e.g., by timing how long the computation take. In this thesis, we focus on two different areas of cryptography. In both parts, we take first a theoretical point of view to obtain a result. We try then to adapt our results so that they are easily usable for implementers and for researchers working in practical cryptography. In the first part of this thesis, we take a look at post-quantum cryptography, i.e., at cryptographic primitives that are believed secure even in the case (reasonably big) quantum computers are built. We introduce HELEN, a new public-key cryptosystem based on the hardness of the learning from parity with noise problem (LPN). To make our results more concrete, we suggest some practical instances which make the system easily implementable. As stated above, the design of cryptographic primitives usually relies on some well-studied hard problems. However, to suggest concrete parameters for these primitives, one needs to know the precise complexity of algorithms solving the underlying hard problem. In this thesis, we focus on two recent hard-problems that became very popular in post-quantum cryptography: the learning with error (LWE) and the learning with rounding problem (LWR). We introduce a new algorithm that solves both problems and provide a careful complexity analysis so that these problems can be used to construct practical cryptographic primitives. In the second part, we look at leakage-resilient cryptography which studies adversaries able to get some side-channel information from a cryptographic primitive. In the past, two main disjoint models were considered. The first one, the threshold probing model, assumes that the adversary can put a limited number of probes in a circuit. He then learns all the values going through these probes. This model was used mostly by theoreticians as it allows very elegant and convenient proofs. The second model, the noisy-leakage model, assumes that every component of the circuit leaks but that the observed signal is noisy. Typically, some Gaussian noise is added to it. According to experiments, this model depicts closely the real behaviour of circuits. Hence, this model is cherished by the practical cryptographic community. In this thesis, we show that making a proof in the first model implies a proof in the second model which unifies the two models and reconciles both communities. We then look at this result with a more practical point-of-view. We show how it can help in the process of evaluating the security of a chip based solely on the more standard mutual information metric.

EPFL2015

Computer Aided Cryptanalysis from Ciphers to Side Channels

Martin Vuagnoux

In this dissertation, we study the security of cryptographic protocols and cryptosystems from the mathematical definition of the primitives, up to their physical implementations in the real world. We propose a representation of the chronological design using six layers (cryptographic primitives, cryptographic protocols, implementation, computer insecurity, side channel cryptanalysis and computer human interactions). We do the assumption that these layers should not be studied independently. Indeed, many negligible security weaknesses coming from different layers can be correlated to provide devastating practical attacks on cryptosystems. However, the complexity of a complete security analysis becomes huge and interdisciplinary knowledge is needed. These limitations are probably the reasons of the lack of complete security analysis in practice. We define a novel approach, to combine and study the six layers simultaneously. We propose to follow the data flow of a system and to perform security analysis across the six layers. This technique is applied in practice to the security analysis of computer keyboards, RC4, IEEE 802.11, and e-passports. Thanks to this method, we found 34 additional exploitable correlations in RC4 and we defined the best key recovery attacks on WEP and WPA. We also identified weaknesses in the design and the implementation of e-passports. Therefore, we show that the security risk of every layer seems to be related to its level of complexity. Thus, the implementation layer, the computer insecurity layer, the side channel layer and the computer human interfaces layer are subject to cost-effective attacks in practice. Interestingly, these layers are not intensively studied in cryptography, where research stays usually focused on the two first layers (and some side channel attacks). In this dissertation, we also propose frameworks for computer aided cryptanalysis. Indeed, when the complexity of a system is too important to perform manual analysis, some tools may automatically find weaknesses. Increasing complexity in systems adds new vulnerabilities. Straightforward but automated analysis becomes relevant. Two frameworks have been developed. The first one automatically highlights linear correlation in RC4. The second framework, called Autodafé automatically detects buffer overflows in modern software, using a technique called Fuzzing by Weighting Attacks with Markers.

EPFL2010

Efficient Cache Attacks on AES, and Countermeasures

Dag Arne Osvik

We describe several software side-channel attacks based on inter-process leakage through the state of the CPU's memory cache. This leakage reveals memory access patterns, which can be used for cryptanalysis of cryptographic primitives that employ data-dependent table lookups. The attacks allow an unprivileged process to attack other processes running in parallel on the same processor, despite partitioning methods such as memory protection, sandboxing, and virtualization. Some of our methods require only the ability to trigger services that perform encryption or MAC using the unknown key, such as encrypted disk partitions or secure network links. Moreover, we demonstrate an extremely strong type of attack, which requires knowledge of neither the specific plaintexts nor ciphertexts and works by merely monitoring the effect of the cryptographic process on the cache. We discuss in detail several attacks on AES and experimentally demonstrate their applicability to real systems, such as OpenSSL and Linux's dm-crypt encrypted partitions (in the latter case, the full key was recovered after just 800 writes to the partition, taking 65 milliseconds). Finally, we discuss a variety of countermeasures which can be used to mitigate such attacks.